topsort + dijkstra 646ms
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 25010, M = 150010, INF = 0x3f3f3f3f;
int T, R, P, S;
int h[N], e[M], w[M], ne[M], idx;
vector<int> block[N];
int bid[N];
int bcnt; // 连通块的个数
int din[N]; // 记录每个连通块的入度
int dist[N];
bool st[N];
queue<int> que; // 定义为全局的变量
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int id) {
bid[u] = id;
block[id].push_back(u);
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (bid[j]) continue;
dfs(j, id);
}
}
void dijkstra(int b_id) {
priority_queue<PII, vector<PII>, greater<PII>> heap;
for (auto x : block[b_id]) heap.push({dist[x], x});
while (!heap.empty()) {
PII cur = heap.top(); heap.pop();
int t = cur.y;
if (st[t]) continue;
st[t] = true;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (bid[j] == bid[t]) heap.push({dist[j], j});
}
if (bid[j] != bid[t] && --din[bid[j]] == 0) que.push(bid[j]);
}
}
}
void topsort() {
memset(dist, 0x3f, sizeof(dist));
dist[S] = 0;
for (int i = 1; i <= bcnt; i++)
if (!din[i]) que.push(i);
while (!que.empty()) {
int t = que.front(); que.pop();
dijkstra(t);
}
}
int main() {
memset(h, -1, sizeof(h));
scanf("%d%d%d%d", &T, &R, &P, &S);
int a, b, c;
while (R--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
for (int i = 1; i <= T; i++) {
if (bid[i]) continue;
dfs(i, ++bcnt);
}
while (P--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
din[bid[b]]++;
}
topsort();
for (int i = 1; i <= T; i++)
if (dist[i] > INF / 2) puts("NO PATH");
else printf("%d\n", dist[i]);
return 0;
}
朴素SPFA 过14个数据TLE
#include <bits/stdc++.h>
using namespace std;
const int N = 25010, M = 150010, INF = 0x3f3f3f3f;
int T, R, P, S;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void spfa() {
memset(dist, 0x3f, sizeof(dist));
queue<int> que;
dist[S] = 0;
que.push(S); st[S] = true;
while (!que.empty()) {
int t = que.front(); que.pop(); st[t] = false;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (!st[j]) que.push(j), st[j] = true;
}
}
}
}
int main() {
memset(h, -1, sizeof(h));
scanf("%d%d%d%d", &T, &R, &P, &S);
int a, b, c;
while (R--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
while (P--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
spfa();
for (int i = 1; i <= T; i++)
if (dist[i] >= INF / 2) puts("NO PATH");
else printf("%d\n", dist[i]);
return 0;
}
SLF优化SPFA 3158ms
#include <bits/stdc++.h>
using namespace std;
const int N = 25010, M = 150010, INF = 0x3f3f3f3f;
int T, R, P, S;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void spfa() {
memset(dist, 0x3f, sizeof(dist));
dist[S] = 0;
deque<int> dq;
dq.push_back(S); st[S] = true;
while (!dq.empty()) {
int t = dq.front(); dq.pop_front(); st[t] = false;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (!st[j]) {
if (dist[j] < dist[dq.front()]) dq.push_front(j); // 类似于双端队列优化
else dq.push_back(j);
st[j] = true;
}
}
}
}
}
int main() {
memset(h, -1, sizeof(h));
scanf("%d%d%d%d", &T, &R, &P, &S);
int a, b, c;
while (R--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
while (P--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
spfa();
for (int i = 1; i <= T; i++)
if (dist[i] >= INF / 2) puts("NO PATH");
else printf("%d\n", dist[i]);
return 0;
}