问题 D: 最短路径
[命题人 : 外部导入]
时间限制 : 1.000 sec 内存限制 : 32 MB
题目描述
有n个城市m条道路（n<1000, m<10000)，每条道路有个长度，请找到从起点s到终点t的最短距离和经过的城市名。
输入
输入包含多组测试数据。
每组第一行输入四个数，分别为n，m，s，t。
接下来m行，每行三个数，分别为两个城市名和距离。
输出
每组输出占两行。
第一行输出起点到终点的最短距离。
第二行输出最短路径上经过的城市名，如果有多条最短路径，输出字典序最小的那条。若不存在从起点到终点的路径，则输出“can’t arrive”。
样例输入 Copy
3 3 1 3
1 3 3
1 2 1
2 3 1
样例输出 Copy
2
1 2 3
分析:
该题是涉及多条最短路径的最短路径问题，由于要输出最短路径，pre定义成vector<int>型数组，在采用dfs遍历最短路径时考虑字典序问题，典型的Dijkstra+Dfs应用。
值得注意一点，据说这题可能会输入重复的边，所以用邻接表在codeup上只能拿50分，建议直接用邻接矩阵。
#include<iostream> #include<vector> #include<algorithm> using namespace std; const int maxv=1001; const int inf=10000000; struct node{ int v,weight; }; vector<node>Adj[maxv] ; bool vis[maxv]; int dis[maxv]; vector<int>pre[maxv];//记录路径 //dijkstra算法 void dijkstra (int n,int s) { fill(vis,vis+n+1,false); fill(dis,dis+n+1,inf); //初始化dis和vis dis[s] =0;//这里求零点到各点最短距离 for(int i=0;i<n;i++) //循环n次 { int min=inf,u=-1; for(int j=1;j<=n;j++) //找最短距离点 ，这里可以用优先队列存储dis下标更快 { if(!vis[j]&&dis[j]<min) { u=j; min=dis[j]; } } if(u==-1) return ;//没有找到 vis[u] =true;//标记已经找到的u for(int j=0;j<Adj[u].size();j++) //更新dis { int x=Adj[u][j].v; if(!vis[x]) { if(dis[u]+Adj[u][j].weight<dis[x]){ dis[x]=dis[u]+Adj[u][j].weight; pre[x].clear(); pre[x].push_back(u);} else if(dis[u]+Adj[u][j].weight==dis[x]) pre[x].push_back(u); } } } } vector<int>path,temppath; void dfs(int s,int t){ if(t==s){ temppath.push_back(t); int k=1,a=path.size(),b=temppath.size(); if(a){ while(a>0&&b>0){ if(temppath[b--]>path[a--]){ k=0;break; } if(temppath[b]<path[a])break; } } if(k)path=temppath; temppath.pop_back(); return; } temppath.push_back(t); for(int i=0;i<pre[t].size();i++) { dfs(s,pre[t][i]); } temppath.pop_back(); } int main(){ int n,m,s,t; int x,y,w; node temp; scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=0;i<m;i++){ scanf("%d%d%d",&x,&y,&w); temp.weight=w; temp.v=x; Adj[y].push_back(temp); temp.v=y; Adj[x].push_back(temp); } dijkstra(n,s); if(dis[t]==inf)printf("can't arrive\n"); else { dfs(s,t); printf("%d\n",dis[t]); for(int i=path.size()-1;i>=0;--i)printf("%d ",path[i]);} return 0; }
