算法理解见：

 

模板:

 

1 #define INF 1000000000 2  3 int N; 4 int dist[101],g[101][101]; 5 int vis[101]; 6 int path[101];    // path[i]表示在最短路径中，i的上一个点 7  8  9 void dijkstra(int start)10 {11     for(int i=1;i<=N;i++)12     {13         dist[i]=INF;14 //        path[i] = -1;    15     }    16     dist[start] = 0;17     memset(vis,0,sizeof(vis));18     19     while(1)20     {21         int mark=-1,mindis=INF;22         for(int i=1;i<=N;i++)23         {24             if(!vis[i]&&dist[i]