不知道哪里有问题(pat 2,4样例没过)
C++ 代码
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 5100, M = N * 2;
int h[N], e[M], ne[M], idx, wp[N], wr[M];
int n, m, c1, c2;
int path[N], group[N];
typedef pair<int, int> PII;
bool in[N];
int cnt[N];
void add(int a, int b, int c)
{
e[idx] = b, wr[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void find(int st, int en)
{
memset(path, 0x3f, sizeof path);
memset(cnt, 0, sizeof cnt);
path[st] = 0;
group[st] = wp[st];
queue<PII> q;
in[st] = true;
cnt[st] = 1;
q.push({st, 0});
while (q.size())
{
PII t = q.front();
q.pop();
int var = t.first, dis = t.second;
in[var] = false;
for (int i = h[var]; i != -1; i = ne[i])
{
int j = e[i];
if (path[j] > path[var] + wr[i])
{
cnt[j] = cnt[var];
path[j] = path[var] + wr[i];
group[j] = group[var] + wp[j];
if (!in[j])
{
q.push({j, path[j]});
in[j] = true;
}
}
else if (path[j] == path[var] + wr[i])
{
cnt[j] += cnt[var];
if (group[j] < group[var] + wp[j])
group[j] = group[var] + wp[j];
}
}
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m >> c1 >> c2;
for (int i = 0; i < n; i++)
cin >> wp[i];
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
find(c1, c2);
if (c1 == c2)
cout << "1 " << wp[c1];
else
cout << cnt[c2] << ' ' << group[c2];
return 0;
}