1 /*  2 Dijkstra计算单源最短路径，并记录路径  3   4 m个点，n条边，每条边上的权值非负，求起点st到终点et的最短路径  5   6 input:  7 n m st et  8 6 10 1 6              9 1 2 6 10 1 3 2 11 1 4 1 12 2 3 6 13 2 5 3 14 3 4 2 15 3 5 2 16 3 6 4 17 4 6 5 18 5 6 3 19  20 output: 21 6 22 1-->4-->6 23 */ 24  25  26  27 #include<iostream> 28 #include<stdio.h> 29 #include<cstring> 30 using namespace std; 31  32 #define INF 0xfffffff 33 #define MAXN 1010 34  35 int n,m;                    /*n:点数,m:边数*/ 36 int st,et;                    /*st:起点,et:终点*/ 37 int  weight[MAXN][MAXN];    /*保存的是边权值*/ 38 int  dis[MAXN];                /*保存源点到任意点之间的最短路*/ 39 int  father[MAXN];            /*保存i点的父亲节点*/ 40 int  vis[MAXN];                /*记录哪些顶点已经求过最短路*/  41  42  43 void input() 44 { 45     scanf("%d%d%d%d",&n,&m,&st,&et); 46     int i,j; 47     for(i=1;i<=n;i++) 48     { 49         for(j=1;j<=n;j++) 50             weight[i][j]=INF; 51         weight[i][i]=0; 52     } 53     int start,end,value; 54     for(i=0;i<m;i++) 55     { 56         scanf("%d%d%d",&start,&end,&value); 57         if(weight[start][end]>value)                        //去重 58             weight[start][end]=weight[end][start]=value;    //无向图 59     } 60 } 61  62 void dijkstra() 63 { 64     int i,j; 65     memset(vis,0,sizeof(vis)); 66     memset(father,0,sizeof(father)); 67      68     //初始化dis数组 69     for(i=1;i<=n;i++) 70         dis[i]=INF; 71     dis[st]=0; 72  73     //枚举n个点     74     for(i=1;i<=n;i++) 75     { 76         int pos=-1; 77  78         //找到未加入集合的最短路的点 79         for(j=1;j<=n;j++) 80             if(!vis[j]&&(pos==-1||dis[j]<dis[pos])) 81                 pos=j; 82  83         //标记这个点已经走过 84         vis[pos]=1; 85  86         //更新dis 87         for(j=1;j<=n;j++) 88             if(!vis[j]&&(dis[j]>dis[pos]+weight[pos][j])) 89             { 90                 dis[j]=dis[pos]+weight[pos][j]; 91                 father[j]=pos; 92             } 93     } 94 } 95  96 void output() 97 { 98     printf("%d\n",dis[et]); 99     int que[MAXN];100     int cnt=0;101     int tmp=et;102     while(father[tmp]!=0)103     {104         que[cnt++]=tmp;105         tmp=father[tmp];106     }107     int i;108     printf("%d",st);109     for(i=cnt-1;i>=0;i--)110         printf("-->%d",que[i]);111     printf("\n");112 }113 114 115 int main()116 {117     input();118     dijkstra();119     output();120     return 0;121 }