【题目链接】
【算法】
SPFA + SLF / LLL 优化
【代码】
#include<bits/stdc++.h>
using namespace std;
#define MAXT 25000 int i,T,R,P,S,u,v,w;
int dist[MAXT+],vis[MAXT+];
vector<pair<int,int> > E[MAXT+]; template <typename T> void read(T &x) {
int f=; char c = getchar(); x=;
for (; !isdigit(c); c = getchar()) { if (c=='-') f=-; }
for (; isdigit(c); c = getchar()) x=x*+c-'';
x*=f;
} inline void SPFA() {
int i,x,to,cost;
deque<int> q;
for (i = ; i <= T; i++) dist[i] = 2e9;
dist[S] = ;
q.push_back(S);
while (!q.empty()) {
x = q.front(); q.pop_front();
vis[x] = ;
for (i = ; i < E[x].size(); i++) {
to = E[x][i].first;
cost = E[x][i].second;
if (dist[x] + cost < dist[to]) {
dist[to] = dist[x] + cost;
if (!vis[to]) {
vis[to] = ;
if ((q.empty()) || (dist[to] > dist[q.front()])) q.push_back(to);
else q.push_front(to);
}
}
}
}
} int main() { read(T); read(R); read(P); read(S); for (i = ; i <= R; i++) {
read(u); read(v); read(w);
E[u].push_back(make_pair(v,w));
E[v].push_back(make_pair(u,w));
}
for (i = ; i <= P; i++) {
read(u); read(v); read(w);
E[u].push_back(make_pair(v,w));
} SPFA(); for (i = ; i <= T; i++) {
if (dist[i] == 2e9)
cout<< "NO PATH" << endl;
else cout<< dist[i] << endl;
} return ; }