题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805073643683840

一道迪杰斯特拉的变形题，之前我这个弱鸡基本只做了模板或接近模板的题。这道题可以很好的帮助我消化最短路径。
在看了一遍题解后自己有敲了一遍，结果还是出现了一些错误，大部分都是比较小的错误。做错过的地方已经注释了

需要求出  最短路径的数量 和 最多召集救援人员的数量与路径

难点是需求的地方比较多，而且救援人员那里刚开始没有读明白。

召集人员数量和最短路径数量都可以通过递推方式来实现

思路：

用way数组记录到达某一点的不同的方式，当前点到达的数量=它已经记录的数量+它前驱的数量（前驱可能改变）

用father数组记录某一个点的前驱

用sumpeple记录调走的人员（当存在多条路径时，人员调走多的更新father，人员调走少的只记录way）

用find函数找回路径。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mapt[510][510];
int father[510];
int way[510]; 
int people[510];
int sum_people[510];
bool vis[510];
int dis[510];
int n,m,s,t;
void find(int a)
{
	if(a==s)//和目的地做对比而不是终点 
	{
		cout<<s; 
		return; 
	}else{
		find(father[a]);
	}
	cout<<' '<<a;
}
void djs()
{
	int i,j;
	for(i=0;i<n;i++)
	{
		int m_len = 0x3f3f3f3f,index = i;
		for(j=0;j<n;j++)
		{
			if(m_len>dis[j]&&!vis[j])//   m_len>dis[i]&&!vis[j]
			{
				m_len = dis[j];
				index = j;
			}
		}
		vis[index]=true;
		
		for(j=0;j<n;j++)
		{
			if(!vis[j]&&dis[j]>dis[index]+mapt[index][j])
			{
				dis[j]=dis[index]+mapt[index][j];
				sum_people[j]=sum_people[index]+people[j];
				vis[j]=false;
				way[j]=way[index];
				father[j]=index;
			}else if(!vis[j]&&dis[j]==dis[index]+mapt[index][j])
			{
				if(sum_people[j]<sum_people[index]+people[j])//用现在召集的+这个点的 
				{
					sum_people[j]=sum_people[index]+people[j];
					father[j]=index;
				}
				way[j]+=way[index];
			}
		}
	}
}
int main()
{
	memset(mapt,0x3f,sizeof mapt);
	int i,a,b,c;
	cin>>n>>m>>s>>t;
	for(i=0;i<n;i++)//这里注意是 0 -  n 
		cin>>people[i];
	for(i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		mapt[a][b]=c;
		mapt[b][a]=c;
	}
	for(i=0;i<n;i++)
	{
		dis[i]=mapt[s][i];
	} 
	dis[s]=0;
	way[s]=1;
	sum_people[s]=people[s];//人数初始 
	djs();
	cout<<way[t]<<' '<<sum_people[t]<<endl;
	find(t);
	return 0; 
}