PTA 城市间紧急救援
题目描述
作为一个城市的应急救援队伍的负责人,你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候,你的任务是带领你的救援队尽快赶往事发地,同时,一路上召集尽可能多的救援队。
输入格式:
输入第一行给出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 <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], w[N], idx;
int p[N]; // p存储每个城市有多少消防员
int d[N], pe[N], dn[N], dc[N]; // dn为走过的城市数量, dc为走过的城市编号, pe为走到每个城市中有的消防员数目
int N1, M, S, D;
bool st[N];
vector<PII> res;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra() // 堆优化版dijkstra()算法
{
memset(d,0x3f, sizeof(d));
priority_queue<PII, vector<PII>, greater<PII> > q;
q.push({0, S});
d[S] = 0;
pe[S] += p[S];
dc[S] = S;
while(q.size())
{
auto u = q.top();
int v = u.y, distance = u.x;
q.pop();
if(st[v]) continue;
st[v] = true;
for(int i = h[v]; i != -1; i = ne[i])
{
int j = e[i];
if (d[j] == d[v] + w[i])
{
if(pe[v] + p[j] > pe[j])
{
dn[j] = dn[v] + 1;
dc[j] = v;
pe[j] = pe[v] + p[j];
// cout << v <<" " << j <<" " << d[j] << " --"<< pe[j] << endl;
}
}
else if(d[j] > d[v] + w[i])
{
dc[j] = v;
dn[j] = dn[v] + 1;
pe[j] = pe[v] + p[j];
d[j] = d[v] + w[i];
q.push({d[j], j});
//cout << v <<" " << j <<" "<< d[j] << " "<< pe[j] << endl;
}
}
}
}
void find(int x) // 伪并查算法
{
if(dc[x] != x)
{
find(dc[x]);
printf("%d ", dc[x]);
}
}
int main()
{
memset(dc, -1, sizeof(dc));
memset(h, -1,sizeof(h));
scanf("%d%d%d%d", &N1, &M, &S, &D);
for(int i = 0; i < N1; i ++ ) scanf("%d", &p[i]);
for(int i = 0; i < M; i ++ )
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
add(a,b,w);add(b,a,w);
}
dijkstra();
printf("%d %d\n", dn[D], pe[D]);
find(D);
printf("%d", D);
return 0;
}
dn 数组有问题