作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。
输入格式:
输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。
第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。
输出格式:
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。
输入样例:
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2输入样例:
2 60
0 1 3本题是很显然的dijkstra()求最短路，我们还要额外维护救援队的数量
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510;
// g 表示两点之间的权重，w 存储这个点的救援队数量
int g[N][N],w[N];
// dist 表示和原点间的最短路，cnt 存储当前点最短路径的数量
// sum 表示当前点可召集的救援队的数量
// pre 存储前驱结点
int dist[N],cnt[N],sum[N],pre[N];
// st 表示已经确定最短路的点
bool st[N];
int n,m,s,d;
void dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[s]=0,cnt[s]=1,sum[s]=w[s];
for(int i=0;i<n-1;i++)
{
int t=-1;
for(int j=0;j<n;j++)
{
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t = j;
}
st[t] = true;
for(int j=0;j<n;j++)
{
// 用t更新，有更短的路径
if(dist[j]>dist[t]+g[t][j])
{
dist[j] = dist[t]+g[t][j];
cnt[j] = cnt[t];//更新后该点的最短路径数等于上一个点的最短路径数
sum[j] = sum[t]+w[j]; //更新救援队数目
pre[j] = t; //更新每个点最短路走过来的上一个点
}
else if(dist[j]==dist[t]+g[t][j])
{
cnt[j]+=cnt[t];//该点加上新路径上一个点的最短路径数
if(sum[j]<sum[t]+w[j])
{
sum[j] = sum[t]+w[j];
pre[j] = t;
}
}
}
}
return;
}
int main(void)
{
cin >> n >> m >> s >>d;
memset(g,0x3f,sizeof g);
for(int i=0;i<n;i++)
cin >> w[i];
while(m--)
{
int a,b,c;
cin >> a >> b >> c;
// 使用邻接矩阵存储无向图
g[a][b]= g[b][a] = min(g[a][b],c);
}
dijkstra();
vector<int> vec;
// 从开始城市到目标城市，pre 储存的前驱结点，所以要倒着存储
for(int i=d;i!=s;i=pre[i]) vec.push_back(i);
// 输出所有的路径和救援队数量
cout << cnt[d] << ' ' << sum[d] << endl;
// cout << vec.size() << endl;
cout << s;
for(int i=vec.size()-1;~i;i--)
cout << ' '<< vec[i];
return 0;
}感谢查看！
