这题是一道给我这个菜鸡复习Dijkstra的好题。
因为要求比较多，先把大致需要的数组罗列一下。
dis[]记录最短路
path[]记录路径
pnum[]记录最短路数目
cnt[]记录最多人数
vis[]记录是否走过这个点
首先需要将vis和cnt置零，dis置∞（用邻接矩记录边也要记得置∞）
接着对起始点初始化，dis[s]=0;path[s]=-1;pnum[s]=1;cnt[s]=s点人数;
从每个点开始，先遍历所有点，如果找到一个没有被访问过的并且距离更近的点，将这点作为起点，进行松弛操作
松弛操作有两种情况，一种是距离较大的情况，更新各个数组即可。如果距离相等，要将两者的pnum[]和cnt[]相加。
因为用了数组记录最短路的每个点前一个节点，所以打印路径递归即可，详见代码
#include <iostream> #include <string.h> #include <cstdio> #include <algorithm> #include <cstdlib> #include <math.h> #include <queue> #include <vector> #define maxn 605 #define INF 0x3f3f3f3f using namespace std; typedef long long ll; int num[maxn],dis[maxn],path[maxn],pnum[maxn],vis[maxn]; int ma[maxn][maxn]; int n,m,s,d,u,v,w; int cnt[maxn]; void dijkstra() { memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); for(int i=0;i<n;i++) dis[i]=INF; dis[s]=0; path[s]=-1; pnum[s]=1; cnt[s]=num[s]; for(int i=0;i<n;i++) { int t,minn=INF; for(int j=0;j<n;j++) { if(!vis[j]&&dis[j]<minn) { t=j; minn=dis[j]; } } vis[t]=1; for(int j=0;j<n;j++) { if(dis[j]>dis[t]+ma[t][j]) { dis[j]=dis[t]+ma[t][j]; path[j]=t; cnt[j]=cnt[t]+num[j]; pnum[j]=pnum[t]; } else if(dis[j]==dis[t]+ma[t][j]) { pnum[j]+=pnum[t]; if(cnt[j]<cnt[t]+num[j]) { cnt[j]=cnt[t]+num[j]; path[j]=t; } } } } } void print(int x) { if(path[x]==-1) { printf("%d",x); return; } print(path[x]); printf(" %d",x); return; } int main() { scanf("%d%d%d%d",&n,&m,&s,&d); memset(ma,INF,sizeof(ma)); for(int i=0;i<n;i++) scanf("%d",&num[i]); for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); ma[u][v]=w; ma[v][u]=w; } dijkstra(); printf("%d %d\n",pnum[d],cnt[d]); print(d); return 0; }
原文：https://www.cnblogs.com/FTA-Macro/p/10499725.html
