这题是一道给我这个菜鸡复习Dijkstra的好题。

因为要求比较多，先把大致需要的数组罗列一下。

dis[]记录最短路

path[]记录路径

pnum[]记录最短路数目

cnt[]记录最多人数

vis[]记录是否走过这个点

首先需要将vis和cnt置零，dis置∞（用邻接矩记录边也要记得置∞）

接着对起始点初始化，dis[s]=0;path[s]=-1;pnum[s]=1;cnt[s]=s点人数;

从每个点开始，先遍历所有点，如果找到一个没有被访问过的并且距离更近的点，将这点作为起点，进行松弛操作

松弛操作有两种情况，一种是距离较大的情况，更新各个数组即可。如果距离相等，要将两者的pnum[]和cnt[]相加。

因为用了数组记录最短路的每个点前一个节点，所以打印路径递归即可，详见代码

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define maxn 605#define INF 0x3f3f3f3fusing 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
              
               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]