景点路线规划系统
项目功能模块
1.输出顶点信息:将各个景点名称输出。
2.输出边的信息:将景点内每两个景点(若两个位置之间有边)的距离输出。
3.修改:修改两个景点(若两个位置之间有边)的距离;
4.求最短路径:输出给定两点之间的最短路径的长度及途经的地点及输出该最短路径所用的时间。
5.删除:删除一条景点路线。
6.插入:插入一条景点路线。
7.添加:添加一个点(景点)或者添加一条边(景点路线)
实现要点
(1)景点分布图采用堆进行存储,对于图中的每一个顶点和每一条边均设置了初值,无需每次运行时手工输入。
(2)采用Dijkstra堆优化算法求解最短路径,为便于操作,用户可以先输出所有的地点及距离。
(3)用户可以随意修改任意两点之间的距离。
(4)用户可以任意增加及删除有效边。
(5)用户可以随意增加或者删除点。
(6)当用户操作错误时,系统会给出相应的出错信息。
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10, INF = 0x3f3f3f3f3f3f3f3fLL; string beauty[N]; struct Edge{int nxt,to,id,w;string c; }e[N << 1]; int head[N], TOT; void add_edge(int u, int v, int w) {e[++TOT].nxt = head[u]; //更新下一点e[TOT].to = v; //当前点指向的下一点e[TOT].w = w; //路径耗费时间head[u] = TOT; //更新当前点e[TOT].c = beauty[v];e[++TOT].nxt = head[v];e[TOT].to = u;e[TOT].w = w;head[v] = TOT;e[TOT].c = beauty[u]; } struct node{//优先队列优化(堆优化)默认从大到小排列int v, c;bool operator<(const node &r) const{//这个函数将从大到小排列改为从小到大return c > r.c;} }; bool vis[N]; int dis[N]; int ffind[N]; void dijkstra(int n,int s) {priority_queue<node> q;for (int i = 1;i <= n; i++) dis[i] = INF, vis[i] = 0;//初始化dis(最短路径),vis(使用路径)dis[s] = 0; //起始点为0ffind[s] = s;q.push({s,0});while (!q.empty()){node temp = q.top(); //temp为此路径的前一个顶点;q.pop();int u = temp.v;if (vis[u]) continue; //该点已经被使用过vis[u] = 1;for (int i = head[u]; i ; i = e[i].nxt){int v = e[i].to, cost = e[i].w;if (!vis[v] && dis[v] > dis[u] + cost){dis[v] = dis[u] + cost;ffind[v] = u;q.push({v,dis[v]});}}} } int jingdian = 1;
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061