題目描述
有n個城市m條道路（n<1000, m<10000)，每條道路有個長度，請找到從起點s到終點t的最短距離和經過的城市名。
輸入
輸入包含多組測試數據。
每組第一行輸入四個數，分別為n，m，s，t。
接下來m行，每行三個數，分別為兩個城市名和距離。
輸出
每組輸出占兩行。
第一行輸出起點到終點的最短距離。
第二行輸出最短路徑上經過的城市名，如果有多條最短路徑，輸出字典序最小的那條。若不存在從起點到終點的路徑，則輸出“can't arrive”。
樣例輸入
3 3 1 3
1 3 3
1 2 1
2 3 1樣例輸出
2
1 2 3分析：《算法筆記》上的 dijkstra + DFS 模板題。注意這道題給出的數據里，兩點之間有多條邊， 之后輸入的邊會覆蓋前面的，每次讀入邊的時候要比較是否是最短的邊。如果用鄰接表，因為會把每條邊都存，就不會有覆蓋的情況。
#include<algorithm>
#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[],vector<int>pre[])
{bool vis[n+5]={0};d[s]=0;for(int times=0;times<n;++times){int u=-1,mini=INF;for(int i=0;i<=n;++i){if(!vis[i]&&d[i]<mini)u=i,mini=d[i];}if(u==-1)return;vis[u]=1;for(int i=0;i<=n;++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(vector<int>pre[],int s,int t,vector<int>&ans,vector<int>temp)
{temp.push_back(t);if(t==s){vector<int>rev;for(int i=temp.size()-1;i>=0;--i){rev.push_back(temp[i]);}if(ans.empty()||rev<ans)ans=rev;return;}for(int i=0;i<pre[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 start=clock();#endif //testint n,m,s,t;while(~scanf("%d%d%d%d",&n,&m,&s,&t)){int d[n+5]={0};vector<int>pre[n+5];for(int i=0;i<=n;++i){d[i]=INF;for(int j=0;j<=n;++j)graph[i][j]=INF;}for(int i=0;i<m;++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("can't arrive\n");else{printf("%d\n",d[t]);vector<int>ans,temp;dfs(pre,s,t,ans,temp);for(int i=0;i<ans.size();++i)printf("%d ",ans[i]);printf("\n");}}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl; //s為單位cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms為單位#endif //testreturn 0;
}
