C++ 代码
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
using PII = pair<int, int>;
using PIII = pair<int, pair<int, int>>;
const int maxn = 1010, maxm = 2e4 + 10;
int n, m;
int h[maxn], e[maxm], w[maxm], ne[maxm], idx;
int dis[2][maxn], cnt[2][maxn], vis[2][maxn];
int s, t;
void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
void dijkstra() {
memset(vis, 0, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
memset(cnt, 0, sizeof(cnt));
dis[0][s] = 0;
cnt[0][s] = 1;
priority_queue<PIII, vector<PIII>, greater<PIII>> q;
q.push({0, {0, s}});
while (q.size()) {
auto t = q.top();
q.pop();
int d1 = t.first, type = t.second.first, u = t.second.second;
if (vis[type][u]) continue;
vis[type][u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i], d = d1 + w[i], num = cnt[type][u];
if (d < dis[0][j]) {
dis[1][j] = dis[0][j];
cnt[1][j] = cnt[0][j];
q.push({dis[1][j], {1, j}});
dis[0][j] = d;
cnt[0][j] = num;
q.push({dis[0][j], {0, j}});
}
else if (d == dis[0][j]) {
cnt[0][j] += num;
}
else if (d < dis[1][j]) {
dis[1][j] = d;
cnt[1][j] = num;
q.push({dis[1][j], {1, j}});
}
else if (d == dis[1][j]) {
cnt[1][j] += num;
}
}
}
}
int main() {
int T;
cin >> T;
while (T--) {
memset(h, -1, sizeof(h));
idx = 0;
cin >> n >> m;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cin >> s >> t;
dijkstra();
int res = cnt[0][t];
if (dis[1][t] == dis[0][t] + 1) res += cnt[1][t];
cout << res << endl;
}
}