题目：
作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。
输入格式:
输入第一行给出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
题解：
写在代码里的，如有问题，欢迎指正
#include <bits/stdc++.h>
#include <string.h>
#include <cstring>
using namespace std;
typedef long long ll;
const int N= 1e3 + 24, inf = 1e9 + 7, M = 1e5+24;
int n, m, s, d;
//其中第i个数是第i个城市的救援队的数目
int num[M];
// 两个城市之间的距离
int sf[N][N];
// s到i最短路径的条数
int cnt[M];
// s 到i最多的救援队数量
int maxx[M];
// i前一个 点，记录路径的
int pre[M];
// s到i的最短距离
int dis[M];
//标记
int vis[M];
void dijistra()
{
// 设置s起点的初始值
dis[s] = 0, maxx[s] = num[s], pre[s] = s, cnt[s] = 1;
int i, j, t, min_dis;
// s到i的最短距离
for(i = 0; i < n; i ++)
{
dis[i] = sf[s][i];
}
while(1)
{
t = -1, min_dis = inf ;
for(i = 0; i < n; i ++)
{
if(vis[i] == 0 && dis[i] < min_dis)
{
min_dis = dis[i];
t = i;
}
}
if(t == -1) break; //找完了
vis[t] = 1; //标记
for(i = 0; i < n; i ++)
{
//未标记
if(vis[i] == 0)
{
if(dis[i] > dis[t] + sf[t][i])
{
dis[i] = dis[t] + sf[t][i]; //距离
cnt[i] = cnt[t]; s到i最短路径的条数，就是前一个的条数
maxx[i] = maxx[t] + num[i]; //s 到i最多的救援队数量，需要加上自己的
pre[i] = t; //标记前一个点
}
else if(dis[i] == dis[t] + sf[t][i])
{
//dis[i] 不用更新
cnt[i] += cnt[t]; //最短路要加上 cnt[t]可达的
if(maxx[t] + num[i] > maxx[i]) //一路上召集尽可能多的救援队,选多的的选择
{
maxx[i] = maxx[t] + num[i];
pre[i] = t; //更新前一个结点
}
}
}
}
}
}
void Print(int de)
{
if(de == pre[s])
{
printf("%d", de);
return;
}
Print(pre[de]); //找de的前一个
printf(" %d", de);
}
int main()
{
int i, j, k, u, v, w;
// 0 ~ n-1
cin >> n >> m >> s >> d;
for(i = 0; i < n; i ++)
{
cin >> num[i];
}
for(i = 0; i < n; i ++)
{
for(j = 0; j < n; j ++)
{
if(i == j) sf[i][j] = 0;
else sf[i][j] = inf;
}
}
// 城市1、城市2、快速道路的长度，
while(m --)
{
cin >> u >> v >> w;
sf[u][v] = w;
sf[v][u] = w;
}
dijistra();
//到d的路径条数 能够召集的最多的救援队数量
cout << cnt[d] << " " << maxx[d] << endl;
//因为记录是前一个结点，递归输出，从d找到s
Print(d);
return 0;
}
