作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。
输入格式: 输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。
第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。
输出格式: 第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。
输入样例:
代码语言：javascript复制4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2输出样例:
代码语言：javascript复制2 60
0 1 3分析 Dijkstra基础应用，比模板单纯求最短路的基础上多了输出路径，路径条数以及多权重（路径相同时人数尽量大），路径只要存每个节点的前驱，然后倒着遍历一遍就行。其他就是一些小细节，看注释。
代码
代码语言：javascript复制// _ooOoo_
// o8888888o
// 88" . "88
// (| -_- |)
// O = /O
// ____/`---'____
// . ' | |// `.
// / ||| : |||//
// / _||||| -:- |||||-
// | | \ - /// | |
// | _| ''---/'' | |
// .-__ `-` ___/-. /
// ___`. .' /--.-- `. . __
// ."" '< `.____<|>_/___.' >'"".
// | | : `- `.;` _ /`;.`/ - ` : | |
// `-. _ __ /__ _/ .-` / /
// ======`-.____`-.________/___.-`____.-'======
// `=---='
//
// .............................................
// 佛祖保佑 一发AC 永无BUG
#include <bits/stdc .h>
#define LL long long
using namespace std;
const int maxn = 1e5 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int n, m, s, d;
//分别为：邻接矩阵存图，是否访问过，到起点的最短距离。
int mp[510][510], vis[510], dis[510]
//分别为：到当前点最多召集几个人，每个城市的人数，存路径，到当前点几条路。
int tot[510], city[510], path[510], road[510];
void dijkstra() {
//别忘初始化
memset(dis, 0x3f, sizeof dis);
tot[s] = city[s];
path[s] = -1;//起点的前驱设为-1
road[s] = 1;//到起点有一种走法
dis[s] = 0;//起点到起点的最短路径为0
priority_queue<PII> q;
q.push({0, s});
while (q.size()) {
int now = q.top().second;
q.pop();
if (vis[now]) continue;
vis[now] = 1;
for (int i = 0; i < n; i ) {
if (mp[now][i]) {
//当存在更小的路时，更新全部信息
if (dis[i] > dis[now] mp[now][i]) {
//i从now这个点过来的路径更短，前驱变为now
path[i] = now;
//从now走过来，则可以召集的人数就是到now可召集的人数 i这个点的人数
tot[i] = tot[now] city[i];
dis[i] = dis[now] mp[now][i];
//到i有几种走法，就到now有几种
road[i] = road[now];
//由于i点最短距离被更新，需要压入队列
q.push({-dis[i], i});
} else if (dis[i] == dis[now] mp[now][i]) {
//有另外的走法使得最短路相同，更新方案数
road[i] = road[now];
//如果可以召集更多的人，更新方案
if (tot[i] < tot[now] city[i]) {
tot[i] = tot[now] city[i];
path[i] = now;
}
}
}
}
}
}
int main(int argc, char const *argv[]) {
cin >> n >> m >> s >> d;
for (int i = 0; i < n; i ) cin >> city[i];
for (int i = 0; i < m; i ) {
int x, y, c;
cin >> x >> y >> c;
mp[x][y] = c;
mp[y][x] = c;
}
dijkstra();
int now = d;
vector<int> ans;
//倒着回溯整条路径，如果前驱为-1说明到起点了
while (now != -1) {
ans.push_back(now);
now = path[now];
}
cout << road[d] << ' ' << tot[d] << endl;
for (int i = ans.size() - 1; i >= 0; i--)
printf("%d%c", ans[i], i == 0 ? 'n' : ' ');
return 0;
}
