题目：紧急救援
思路：
看下问题：
（1）求最短路径；
（2）记录不同最短路径的个数即最短路径可能存在多条相同的值，但路径不同；
（3）在最短路径的基础上筛选人数最多的一条路径；
（4）记录路径。
求解：
利用最基本的Dijkstra直接可求出问题（1）；
而问题（2）和（3）其实同解问题（1）一样，只需再添加俩个数组，分别记录到每个点路径个数和人数即可。
记录路径条数：当筛选最短路径时，只需记录将当前路径个数数组等于上一步的路径个数即可，而当出现相等的路径时，将上一步的路径个数累加到当前路径个数数组。
记录人数：只需当出现相等的最优解路径时，进行比较当前的人数后更新最优解人数即可。
而问题（4）就是同链表一样，记录上一结点即可：只需每次进行选取最优解时用一个数组进行记录上一步的位置即可，因为每个点只出现一次，所有记录路径时不会出现覆盖情况。
参考：_TCgogogo_博客
代码：
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; const int maxn = 505; const int inf = 999999999; int n,g[maxn][maxn],person[maxn]; int dis[maxn],pathNum[maxn],tolpes[maxn],visit[maxn],path[maxn]; void init(){//初始化图的所有路径都为无穷大 for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i == j) g[i][j] = 0;else g[i][j]= inf; } void Dijkstra(int s){ for(int i=0;i<n;i++){ dis[i] = g[s][i];//将s到其他点的路径值保存到数组中，数组的下标分别代表s到i路径的距离 if(dis[i] != inf){//如果当前路径有路，进行记录路径条数和人数 pathNum[i] = 1;//s到i可通，条数1 tolpes[i] = person[s] + person[i];//将s到i的人数记录 } } memset(visit,0,sizeof(visit));//标记数组置0 visit[s] = 1;//标记源点 for(int i=0;i<n;i++){ int minn = inf,record; for(int j=0;j<n;j++)//寻找s到其他点中路径最小的那个点作为下一个走到的点 if(dis[j] < minn && !visit[j]){minn = dis[j];record = j;} visit[record] = 1;//标记当前走到的点 for(int j=0;j<n;j++){//用当前点到其他点与最优解比较，更新最优解 if(visit[j]) continue; if(g[record][j] + dis[record] < dis[j]){//当前点到j点加上s到当前点的路径与当前j的最优解进行比较 dis[j] = dis[record] + g[record][j];//更新最优解路径 tolpes[j] = person[j] + tolpes[record];//更新人数 pathNum[j] = pathNum[record];//因为没有达到相同的最优解，所有当前的不同路径条数还是上一步的条数 path[j] =record;//记录路径，每次记录上一节点 } else if(g[record][j] + dis[record] == dis[j] && record != j){//当最优解相等时说明要更新条数和人数了 pathNum[j]+=pathNum[record];//将上一步的条数都累加到本次！ if(person[j] + tolpes[record] > tolpes[j]){//筛选人数最优解 tolpes[j] = person[j] + tolpes[record]; path[j] = record;//记录路径 } } } } } int main() { int m,s,d,u,v,l; while(~scanf("%d%d%d%d",&n,&m,&s,&d)){ init(); for(int i=0;i<n;i++) scanf("%d",&person[i]); for(int i=0;i<m;i++){ scanf("%d%d%d",&u,&v,&l); g[u][v] = g[v][u] = l; } Dijkstra(s); int prtPath[maxn],cnt = 0; printf("%d %d\n",pathNum[d],tolpes[d]); //将路径找出来 prtPath[cnt++] = d; while(path[d] != s){ d = path[d]; prtPath[cnt++] = d; } prtPath[cnt++] = s; while(--cnt) printf("%d ",prtPath[cnt]);printf("%d\n",prtPath[cnt]); } return 0; }