建设农产品网站总结ppt模板,如何打开wordpress,app开发的流程,网站设计公司 无锡题目描述
有n个城市m条道路#xff08;n1000, m10000)#xff0c;每条道路有个长度#xff0c;请找到从起点s到终点t的最短距离和经过的城市名。
输入
输入包含多组测试数据。
每组第一行输入四个数#xff0c;分别为n#xff0c;m#xff0c;s#xff0c;t…题目描述
有n个城市m条道路n1000, m10000)每条道路有个长度请找到从起点s到终点t的最短距离和经过的城市名。
输入
输入包含多组测试数据。
每组第一行输入四个数分别为nmst。
接下来m行每行三个数分别为两个城市名和距离。
输出
每组输出占两行。
第一行输出起点到终点的最短距离。
第二行输出最短路径上经过的城市名如果有多条最短路径输出字典序最小的那条。若不存在从起点到终点的路径则输出“cant arrive”。
样例输入
3 3 1 3
1 3 3
1 2 1
2 3 1
样例输出
2
1 2 3
分析《算法笔记》上的 dijkstra DFS 模板题。注意这道题给出的数据里两点之间有多条边 之后输入的边会覆盖前面的每次读入边的时候要比较是否是最短的边。如果用邻接表因为会把每条边都存就不会有覆盖的情况。
#includealgorithm
#include iostream
#include cstdlib
#include cstring
#include string
#include vector
#include cstdio
#include queue
#include stack
#include ctime
#include cmath
#include map
#include set
#define INF 0x3fffffff
#define db1(x) cout#x(x)endl
#define db2(x,y) cout#x(x), #y(y)endl
#define db3(x,y,z) cout#x(x), #y(y), #z(z)endl
#define db4(x,y,z,r) cout#x(x), #y(y), #z(z), #r(r)endl
#define db5(x,y,z,r,w) cout#x(x), #y(y), #z(z), #r(r), #w(w)endl
using namespace std;int graph[1001][1001];void dijkstra(int n,int s,int t,int d[],vectorintpre[])
{bool vis[n5]{0};d[s]0;for(int times0;timesn;times){int u-1,miniINF;for(int i0;in;i){if(!vis[i]d[i]mini)ui,minid[i];}if(u-1)return;vis[u]1;for(int i0;in;i){if(!vis[i]graph[u][i]!INF){if(d[i]d[u]graph[u][i]){d[i]d[u]graph[u][i];pre[i].clear();pre[i].push_back(u);}else if(d[i]d[u]graph[u][i]){pre[i].push_back(u);}}}}
}
//用一个vector存储路径经过的点序列保留字典序最小的
void dfs(vectorintpre[],int s,int t,vectorintans,vectorinttemp)
{temp.push_back(t);if(ts){vectorintrev;for(int itemp.size()-1;i0;--i){rev.push_back(temp[i]);}if(ans.empty()||revans)ansrev;return;}for(int i0;ipre[t].size();i){dfs(pre,s,pre[t][i],ans,temp);}
}int main(void)
{#ifdef testfreopen(in.txt,r,stdin);
// freopen(out.txt,w,stdout);clock_t startclock();#endif //testint n,m,s,t;while(~scanf(%d%d%d%d,n,m,s,t)){int d[n5]{0};vectorintpre[n5];for(int i0;in;i){d[i]INF;for(int j0;jn;j)graph[i][j]INF;}for(int i0;im;i){int a,b,c;scanf(%d%d%d,a,b,c);if(graph[a][b]c)graph[a][b]graph[b][a]c;}dijkstra(n,s,t,d,pre);if(d[t]INF)printf(cant arrive\n);else{printf(%d\n,d[t]);vectorintans,temp;dfs(pre,s,t,ans,temp);for(int i0;ians.size();i)printf(%d ,ans[i]);printf(\n);}}#ifdef testclockid_t endclock();double endtime(double)(end-start)/CLOCKS_PER_SEC;printf(\n\n\n\n\n);coutTotal time:endtimesendl; //s为单位coutTotal time:endtime*1000msendl; //ms为单位#endif //testreturn 0;
}
