题目描述
有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
/*
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<iostream>
using namespace std;
const int MAXV=1010;
const int INF=1000000000;
int G[MAXV][MAXV];
bool vis[MAXV]={false};
int pre[MAXV];
int d[MAXV];void Dij(int s,int n){fill(d,d+MAXV,INF);d[s]=0;
// printf("dddd\n");
// vis[s]=true;for(int i=1;i<=n;i++){// for(int k=1;k<=n;k++)printf("d[%d]=%d\n",k,d[k]);int u=-1,MIN;MIN=INF;for(int j=1;j<=n;j++){ if(d[j]<MIN&&vis[j]==false){u=j;MIN=d[u];// printf("if:MIN=%d u=%d d[%d]=%d\n",MIN,u,u,d[u]);} }// printf("\n---------------\n");// printf("\nMIN=%d u=%d d[%d]=%d\n",MIN,u,u,d[u]);if(u==-1)return;vis[u]=true;//for(int j=1;j<=n;j++)pre[j]=j;for(int j=1;j<=n;j++){if(vis[j]==false&&G[u][j]!=INF){if(d[j]>d[u]+G[u][j]){d[j]=d[u]+G[u][j];//printf("%d: d=%d \n",j,d[j]);// pre[j].push_back(u);pre[j]=u;}else if(d[j]==d[u]+G[u][j]&&pre[j]>u){// pre[j].push_back(u);pre[j]=u;}}}}
}
void DFS(int s,int v){if(v==s){printf("%d ",s);return;}DFS(s,pre[v]);printf("%d ",v);
}
int main(){int n,s,z,m;while(scanf("%d %d %d %d",&n,&m,&s,&z)!=EOF){getchar();fill(d,d+MAXV,INF);fill(G[0],G[0]+MAXV*MAXV,INF);for(int i=1;i<=n;i++){pre[i]=i;vis[i]=false;}int a,b,w;while(m--){scanf("%d %d %d",&a,&b,&w);getchar();if(G[a][b]==INF){G[a][b]=w;G[b][a]=w; }else{if(G[a][b]>w){G[a][b]=w;G[b][a]=w;}}}/*for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d ",G[i][j]);printf("\n");}Dij(s,n);if(d[z]!=INF){printf("%d\n",d[z]);DFS(s,z); }else printf("can't arrive");printf("\n");}
/* cout<<strcmp("a","b")<<endl; -1cout<<strcmp("b","a")<<endl; 1cout<<strcmp("123","13")<<endl;-1return 0;
}*/#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
bool vis[maxn];
int n,d[maxn],G[maxn][maxn],pre[maxn];
struct node
{int v,w;node(int x,int y):v(x),w(y){ };
};
vector<node> adj[maxn];
void Dijkstra(int s)
{fill(d,d+maxn,INF);fill(vis,vis+maxn,false);for(int i=1;i<=n;++i)pre[i]=i;d[s]=0;for(int i=1;i<=n;++i){int min=INF,u=-1;for(int j=1;j<=n;++j){if(d[j]<min&&vis[j]==false){u=j;min=d[j];}}if(u==-1)return ;vis[u]=true;for(int j=0;j<adj[u].size();++j){int v=adj[u][j].v;if(vis[v]==false){if(d[u]+adj[u][j].w<d[v]){d[v]=d[u]+adj[u][j].w;pre[v]=u;}else if(d[u]+adj[u][j].w==d[v]&&u<pre[v]){pre[v]=u;}}}}
}void DFS(int v,int s)
{if(v==s){printf("%d ",v);return ;}DFS(pre[v],s);printf("%d ",v);
}
int main()
{int m,s,t,d1,d2,w;while(~scanf("%d %d %d %d",&n,&m,&s,&t)){for (int i=1;i<=n;++i)adj[i].clear();for(int i=0;i<m;++i){scanf("%d %d %d",&d1,&d2,&w);adj[d1].push_back(node(d2,w));adj[d2].push_back(node(d1,w));}Dijkstra(s);if(d[t]==INF){printf("can't arrive\n");}else{printf("%d\n",d[t]);DFS(t,s);printf("\n");}}return 0;
}
对题目中的字典序最小保持疑问，关于字典序最小的处理是借鉴网上的AC代码的，但还是很疑惑：
如图：1<-(2)->3<-(1)->2<-(1)->1,1到3的路径有1->3和1->2->3长度都为2，但是字典序小的难道不是1->2->3嘛，但按AC的代码是13？？（虽然代码AC了，但是还是不知道为什么，希望大佬能解释一下，谢谢。