题目：
本题使用Dijkstra算法，但在模板上进行了一定的扩展，是一道不错的最短路题目。
AC代码：
1 #include 2 #include 3 #include 4 #include 5 #include<string> 6 using namespace std; 7 int n,m,start,ed; 8 int p[550];//550是防止越界，也可以写510什么的，看个人习惯 9 int g[550][550]; 10 int cnt[550],sum[550];//cnt 是最短路径数 sum是救援队数量 11 bool st[550];//标志这个点是否抵达过 12 int f[550];//记录的是经过的点，这题可以理解成记录下标 13 int dist[550]; 14 void print(int start,int ed) 15 { 16 if(ed==start) 17 { 18 cout<<start; 19 return;//起点就是终点 20 } 21 print(start,f[ed]);//递归不断回去,注意用DFS思想，从深向浅递归 22 cout<<" "<<ed; 23 } 24 void dj() 25 { 26 memset(dist,0x3f,sizeof dist); 27 dist[start]=0,cnt[start]=1,sum[start]=p[start];//初始化 28 for(int i=0;i) 29 { 30 int t=-1; 31 for(int j=0;j) 32 { 33 if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;//取最短点 34 } 35 st[t]=true; 36 for(int j=0;j) 37 { 38 if(dist[j]>dist[t]+g[t][j])//就是最短路变化 39 { 40 f[j]=t;//记录路径,从t到j 41 dist[j]=dist[t]+g[t][j];//变化最短路 42 cnt[j]=cnt[t];//变化次数 43 sum[j]=sum[t]+p[j];//最短路径变化后 44 } 45 else if(dist[j]==dist[t]+g[t][j]) 46 { 47 if(sum[j]//救援队少的时候，变化路径 48 { 49 f[j]=t; 50 sum[j]=sum[t]+p[j]; 51 } 52 cnt[j]=cnt[j]+cnt[t];//两个最短路方式的相加 53 } 54 } 55 } 56 } 57 int main() 58 { 59 cin>>n>>m>>start>>ed; 60 for(int i=0;i>p[i]; 61 memset(g,0x3f,sizeof g);//设现在每一个城市间为正无穷的距离 62 for(int i=0;i) 63 { 64 int a,b,c; 65 cin>>a>>b>>c; 66 g[a][b]=g[b][a]=min(g[a][b],c);//防止重边 67 } 68 dj(); 69 cout<" "<endl; 70 print(start,ed); 71 return 0; 72 }