2623 - 最短路径
有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
C语言解答
#include <stdio.h> #include <stdlib.h> #include <string.h> #define maxn 15 #define INF 1000000000 int G[maxn][maxn]; int d[maxn],vis[maxn],path[maxn]; int n; void dijkstra(){ d[1]=0; for(int i = 0;i < n; i++){ int u = -1, min = INF; for(int j = 1;j <= n; j++){ if(vis[j]==0 && d[j] < min){ u = j; min = d[j]; } } if(u == n)return; vis[u]=1; for(int v = 1;v <= n; v++){ if(vis[v]==0 && G[u][v] != INF){ if(d[u]+G[u][v]<d[v]){ d[v] = d[u] + G[u][v]; path[v] = u; } else if(d[u] + G[u][v] == d[v]){ if(path[v]>u)path[v]=u; } } } } } void print(int i){ if(i<=0)return; print(path[i]); if(i==n)printf("%d\n",n); else printf("%d ",i); } int main() { scanf("%d",&n); for(int i = 0;i <= n;i++)d[i]=INF; memset(vis,0,sizeof(vis)); memset(path,0,sizeof(path)); for(int i = 1;i <= n; i++){ for(int j = 1;j <= n; j++){ int temp; scanf("%d",&temp); if(temp==0)G[i][j]=INF; else G[i][j]=temp; } } dijkstra(); printf("minlong=%d\n",d[n]); print(n); return 0; }