BZOJ2200

聽說加上slf優化的spfa的卡過，真的不想寫這些東西。

考慮使用堆優化的dij算法。

先加上所有雙向邊，然后dfs一下搜出所有由雙向邊構成的聯通塊，然后加上所有的單向邊，一邊對所有聯通塊拓撲排序一邊在聯通塊內部處理最短路，因為所有的雙向邊都是不帶負權的，而單向邊都是有負權的，所以這樣規避dij貪心的錯誤之處。

注意到一個$inf$可能被另一個$inf$加上一個負權邊拓展得到，所以最后的答案可能會小于$inf$，檢驗的時候注意取的極大值要小于一開始賦的$inf$。

時間復雜度$O(nlogn)$。

Code：

#include <cstdio> #include <cstring> #include <queue> #include <iostream> #include <vector> using namespace std; typedef pair <int, int> pin;const int N = 25005; const int M = 2e5 + 5; const int inf = 1e8;int n, m1, m2, st, tot = 0, head[N], dis[N]; int l = 1, r = 0, q[N], deg[N], sccCnt = 0, bel[N]; bool vis[N]; vector <int> scc[N];struct Edge {int to, nxt, val; } e[M];inline void add(int from, int to, int val) {e[++tot].to = to;e[tot].val = val;e[tot].nxt = head[from];head[from] = tot; }template <typename T> inline void read(T &X) {X = 0; char ch = 0; T op = 1;for(; ch > '9'|| ch < '0'; ch = getchar())if(ch == '-') op = -1;for(; ch >= '0' && ch <= '9'; ch = getchar())X = (X << 3) + (X << 1) + ch - 48;X *= op; }void dfs(int x) {bel[x] = sccCnt, scc[sccCnt].push_back(x);for(int i = head[x]; i; i = e[i].nxt) {int y = e[i].to;if(!bel[y]) dfs(y);} }priority_queue <pin> Q; void dij(int c) {for(unsigned int i = 0; i < scc[c].size(); i++) Q.push(pin(-dis[scc[c][i]], scc[c][i]));for(; !Q.empty(); ) {int x = Q.top().second; Q.pop();if(vis[x]) continue;vis[x] = 1;for(int i = head[x]; i; i = e[i].nxt) {int y = e[i].to;if(bel[y] == c) {if(dis[y] > dis[x] + e[i].val) {dis[y] = dis[x] + e[i].val;Q.push(pin(-dis[y], y));}} else {if(dis[y] > dis[x] + e[i].val) dis[y] = dis[x] + e[i].val;deg[bel[y]]--;if(!deg[bel[y]]) q[++r] = bel[y]; }}} }int main() {read(n), read(m1), read(m2), read(st);for(int x, y, v, i = 1; i <= m1; i++) {read(x), read(y), read(v);add(x, y, v), add(y, x, v);}for(int i = 1; i <= n; i++)if(!bel[i]) ++sccCnt, dfs(i);for(int x, y, v, i = 1; i <= m2; i++) {read(x), read(y), read(v);add(x, y, v);deg[bel[y]]++;}for(int i = 1; i <= sccCnt; i++)if(!deg[i]) q[++r] = i;memset(dis, 0x3f, sizeof(dis)); dis[st] = 0;for(; l <= r; ++l) dij(q[l]);for(int i = 1; i <= n; i++) {if(dis[i] > inf) puts("NO PATH");else printf("%d\n", dis[i]);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/CzxingcHen/p/9562972.html

總結

以上是生活随笔為你收集整理的Luogu 3008 [USACO11JAN]道路和飞机Roads and Planes的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。