SPFA+SLF优化,直接朴素的SPFA会卡掉。
当然用SPFA+LLL+SLF应该也是可以的,但是我不是很会LLL,但是一个SLF优化就可以过了。
题目当中说:双向边是非负的而单向边没有环,所以,我们可以先把有双向边链接的若干个点缩成一个点,然后点之间连上单向边之后这张图是一个有向无环图,所以跑广搜就可以了。而连通块内部因为边非负,所以可以dijkstra。
#include<iostream> #include<string> #include<math.h> #include<algorithm> #include<vector> #include<queue> #include<bits/stdc++.h> typedef long long ll; #define INF 0x3f3f3f3f ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a * b / (gcd(a, b)); } #define PII pair<int,int> using namespace std; const int N = 2e6 + 10, mod = 1e9 + 7; int qmi(int a, int k, int p) //快速幂模板 { int res = 1; while (k) { if (k & 1) res = (ll)res * a % p; k >>= 1; a = (ll)a * a % p; } return res; } /////////////////////////////////////////////////////////// int n,m,w; int T, R, P, S; struct Edge { int v, w, next; }edge[N]; int head[N], dis[N], t; bool vis[N]; void init(){ memset(dis, 0x3f, sizeof dis); } inline void Add_edge(int u, int v, int w) { edge[++t].next= head[u]; head[u] = t; edge[t].v = v; edge[t].w = w; } inline void SPFA() { deque <int> q; q.push_front(S); dis[S] = 0; while (!q.empty()) { int now = q.front(); q.pop_front(); vis[now] = 0; for (int i = head[now]; i; i = edge[i].next) { if (dis[edge[i].v] <= edge[i].w + dis[now]) continue; dis[edge[i].v] = edge[i].w + dis[now]; if (vis[edge[i].v]) continue; vis[edge[i].v] = 1; if (q.empty() || dis[edge[i].v] <= dis[q.front()]) q.push_front(edge[i].v); else q.push_back(edge[i].v); } } } int main() { cin>>T>>R>>P>>S; while (R--) { int a,b,c; cin>>a>>b>>c; Add_edge(a, b, c), Add_edge(b, a, c); } while (P--) { int a,b,c; cin>>a>>b>>c; Add_edge(a, b, c); } init(); SPFA(); for (int i = 1; i <= T; ++i) { if (dis[i] == INF) { cout<<"NO PATH"<<endl; } else { cout<<dis[i]<<endl; } } return 0; }