作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。
输入格式：
输入第一行给出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算法，并且用优先队列来优化，便于最小dist的查找
注意当找到一条与当前路径长度相等的新路时，路的总条数并不是加1，而是加上到上一个点的路径条数
注意走到起点的路的条数要初始化为1
#include <iostream>
#include <queue>
#include <cstring>
#define INF 1000
#define N 510
using namespace std;
struct node {
int num, val;
friend bool operator<(node a, node b)
{
return a.val>b.val;
}
};
int visited[N];
int dis[N];
int edge[N][N];
int numpeo[N];
int maxpeo[N];
int cur[N];//当前最短路径长度
int pnum[N];//最大召集数情况下的上一个点
priority_queue<node> que;
int n, m, s, d;
void Dijkstra(int s, int t)
{
cur[s] = 1;//注意这步的初始化不要漏
pnum[s] = -1;//源点的上一个点，输出路径时会用到
dis[s] = 0;
node no;
no.num = s;
no.val = 0;
que.push(no);
//要访问t的时说明能走到t的所有路径都访问过了
while (!que.empty()) {
while (visited[que.top().num]) que.pop();
visited[que.top().num] = 1;
if (que.top().num == t)
break;
for (int i = 0; i < n;++i)
if ((!visited[i]) && edge[que.top().num][i]!=-1) {
//注意此处循环到是也会跳过因为已经visited过了
//所以不用怕cur会因为循环到自己了边是0导致长度相等而加1
if (dis[i] == dis[que.top().num] + edge[que.top().num][i]) {
cur[i]+=cur[que.top().num];//注意此处并不是加1
if (maxpeo[i] < maxpeo[que.top().num] + numpeo[i]) {
maxpeo[i] = maxpeo[que.top().num] + numpeo[i];
pnum[i] = que.top().num;
}
}
if (dis[i] > dis[que.top().num] + edge[que.top().num][i]) {
dis[i] = dis[que.top().num] + edge[que.top().num][i];
cur[i] = cur[que.top().num];//注意这步并不是更新为1
pnum[i] = que.top().num;
maxpeo[i] = maxpeo[que.top().num] + numpeo[i];
no.num = i;
no.val = dis[i];
que.push(no);
}
}
que.pop();
}
}
int main()
{
cin >> n >> m >> s >> d;
memset(visited, 0, sizeof(visited));
//调试的是后发现dis全被初始化成一个很大的负值
//关于memset的问题在其他笔记里另写
memset(dis, 127, sizeof(dis));
memset(edge, -1, sizeof(edge));
memset(cur, 0, sizeof(cur));
for (int i = 0; i < n; ++i) {
cin >> numpeo[i];
maxpeo[i] = numpeo[i];
edge[i][i] = 0;
}
for (int i = 1; i <= m; ++i)
{
int start, end, length;
cin >> start >> end >> length;
edge[start][end] = edge[end][start] = length;
}
Dijkstra(s, d);
cout << cur[d] << " " << maxpeo[d]<<endl;
int p = d;
int path[N];
int num=-1;
while (p!=-1) {
++num;
path[num] = p;
p = pnum[p];
}
for (int i = num; i >= 0; --i) {
cout << path[i];
if (i)
cout << " ";
}
system("pause");
return 0;
}
