->點(diǎn)我進(jìn)原題

[Usaco2011 Jan]道路和航線

---

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 1116 Solved: 410

---

Description

Farmer John正在一個(gè)新的銷售區(qū)域?qū)λ呐Ｄ啼N售方案進(jìn)行調(diào)查。他想把牛奶送到T個(gè)城鎮(zhèn) (\(1 <= T <= 25,000\))，編號(hào)為\(1\)~\(T\)。這些城鎮(zhèn)之間通過(guò)\(R\)條道路 (\(1 <= R <= 50,000\)，編號(hào)為\(1\)到\(R\)) 和\(P\)條航線 (\(1 <= P <= 50,000\)，編號(hào)為\(1\)到\(P\)) 連接。每條道路i或者航線i連接城鎮(zhèn)\(A_i\) (\(1 <= A_i <= T\))到\(B_i\) (\(1 <= B_i <= T\))，花費(fèi)為\(C_i\)。對(duì)于道路，\(0 <= C_i <= 10,000\);然而航線的花費(fèi)很神奇，花費(fèi)\(C_i\)可能是負(fù)數(shù)(\(-10,000 <= C_i <= 10,000\))。道路是雙向的，可以從\(A_i\)到\(B_i\)，也可以從\(B_i\)到\(A_i\)，花費(fèi)都是\(C_i\)。然而航線與之不同，只可以從\(A_i\)到\(B_i\)。事實(shí)上，由于最近恐怖主義太囂張，為了社會(huì)和諧，出臺(tái) 了一些政策保證：如果有一條航線可以從\(A_i\)到\(B_i\)，那么保證不可能通過(guò)一些道路和航線從\(B_i\)回到\(A_i\)。由于FJ的奶牛世界公認(rèn)十分給力，他需要運(yùn)送奶牛到每一個(gè)城鎮(zhèn)。他想找到從發(fā)送中心城鎮(zhèn)\(S\)(\(1 <= S <= T\)) 把奶牛送到每個(gè)城鎮(zhèn)的最便宜的方案，或者知道這是不可能的。

Input

第\(1\)行：四個(gè)空格隔開(kāi)的整數(shù): \(T\), \(R\), \(P\), and \(S\)
第\(2到R+1\)行：三個(gè)空格隔開(kāi)的整數(shù)（表示一條道路）：\(A_i\), \(B_i\) 和 \(C_i\)
第\(R+2到R+P+1\)行：三個(gè)空格隔開(kāi)的整數(shù)（表示一條航線）：\(A_i\), \(B_i\) 和 \(C_i\)

Output

第\(1到T\)行：從\(S\)到達(dá)城鎮(zhèn)\(i\)的最小花費(fèi)，如果不存在輸出"NO PATH"。

Sample Input

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

樣例輸入解釋：

一共六個(gè)城鎮(zhèn)。在\(1-2，3-4，5-6\)之間有道路，花費(fèi)分別是\(5，5，10\)。同時(shí)有三條航線：\(3\)->\(5\)，
\(4\)->\(6\)和\(1\)->\(3\)，花費(fèi)分別是-\(100\)，-\(100\)，-\(10\)。\(FJ\)的中心城鎮(zhèn)在城鎮(zhèn)\(4\)。

Sample Output

NO PATH
NO PATH
5
0
-95
-100

樣例輸出解釋：

\(FJ\)的奶牛從\(4\)號(hào)城鎮(zhèn)開(kāi)始，可以通過(guò)道路到達(dá)\(3\)號(hào)城鎮(zhèn)。然后他們會(huì)通過(guò)航線達(dá)到\(5\)和\(6\)號(hào)城鎮(zhèn)。
但是不可能到達(dá)\(1\)和\(2\)號(hào)城鎮(zhèn)。

分析

法\(1\)：Dijkstra+Topsort

本題是一道明顯的單源最短路問(wèn)題，但圖中帶有負(fù)權(quán)邊，不能使用Dijkstra算法。若直接用SPFA算法求解，因?yàn)闇y(cè)試數(shù)據(jù)經(jīng)過(guò)了特殊構(gòu)造，所以程序無(wú)法在規(guī)定時(shí)限內(nèi)輸出答案。題目中有一個(gè)特殊條件——雙向邊都是非負(fù)的，只有單向邊可能是負(fù)的，并且單向邊不構(gòu)成環(huán)。我們應(yīng)該利用這個(gè)性質(zhì)來(lái)解答本題。
如果只把雙向邊（道路）添加到圖里，那么會(huì)形成若干個(gè)連通塊。若把每個(gè)連通塊整體看作一個(gè)“點(diǎn)”,再把單向邊（航線）添加到圖里，會(huì)得到一張有向無(wú)環(huán)圖。在有向無(wú)環(huán)圖中，無(wú)論邊權(quán)正負(fù)，都可以按照拓?fù)渑判蜻M(jìn)行掃描，在線性時(shí)間內(nèi)求出單源最短路。這啟發(fā)我們用拓?fù)渑判虻目蚣芴幚碚麄€(gè)圖，但在雙向邊構(gòu)成的每個(gè)連通塊內(nèi)部使用堆優(yōu)化的Dijkstra算法快速計(jì)算該塊內(nèi)的最短路信息
這樣就可以在塊內(nèi)使用Dijkstra，塊間利用拓?fù)渑判蚋麓鸢浮r(shí)間復(fù)雜度\(O(MlogN)\)。

法\(2\)：SPFA+SLF

順便加上了一些卡常的奇技淫巧，最慢的點(diǎn)為732ms，如果不了解SLF優(yōu)化的可以看我的另外一篇博客->戳我

代碼

法\(1\)：

#include<cstdio> #include<cctype> #include<algorithm> #include<iostream> #include<queue> #include<bits/stdc++.h> #define rg register using namespace std; inline int read(){rg int f=0,x=0;rg char ch=getchar();while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return f?-x:x; }const int N =25010; const int M =100010; const int inf =0x7f7f7f7f; #define ft first #define sd second int n,r,p,s,head[N],tot; int cnt,belong[N]; int indeg[N],dis[N]; bool vis[N]; typedef pair<int ,int > pa; vector <pa >road[N],plane[N]; vector <int >block[N]; inline void init(){for(rg int i=0;i<N;++i) dis[i]=inf;dis[s]=0; } inline void dfs(rg int u){belong[u]=cnt;block[cnt].push_back(u);for(int i=0;i<road[u].size();++i){int v=road[u][i].ft;if(!belong[v]) dfs(v);} } inline void topsort_dij(){init();queue<int > q;for(rg int i=1;i<=cnt;++i) if(!indeg[i]) q.push(i);while(!q.empty()){int u=q.front();q.pop();priority_queue<pa,vector<pa>,greater<pa> > pq;for(int i=0;i<block[u].size();++i)if(dis[block[u][i]]!=inf)pq.push(make_pair(dis[block[u][i]],block[u][i]));while(!pq.empty()){int u=pq.top().sd;pq.pop();if(vis[u]) continue;vis[u]=true;for(int i=0;i<road[u].size();++i)if(dis[u]+road[u][i].sd<dis[road[u][i].ft])pq.push(make_pair(dis[road[u][i].ft]=dis[u]+road[u][i].sd,road[u][i].ft));for(int i=0;i<plane[u].size();++i)dis[plane[u][i].ft]=min(dis[plane[u][i].ft],dis[u]+plane[u][i].sd);}for(int i=0;i<block[u].size();++i)for(int j=0;j<plane[block[u][i]].size();++j)if(--indeg[belong[plane[block[u][i]][j].ft]]==0)q.push(belong[plane[block[u][i]][j].ft]);} } signed main(){n=read(),r=read(),p=read(),s=read();for(rg int i=1,u,v,w;i<=r;++i){u=read(),v=read(),w=read();road[u].push_back(make_pair(v,w));road[v].push_back(make_pair(u,w));}for(rg int i=1;i<=n;++i)if(!belong[i]){++cnt;dfs(i);}for(rg int i=1,u,v,w;i<=p;++i){u=read(),v=read(),w=read();plane[u].push_back(make_pair(v,w));++indeg[belong[v]];}topsort_dij(); for(rg int i=1;i<=n;++i)if(dis[i]==inf) printf("NO PATH\n");else printf("%d\n",dis[i]);return 0; }

法\(2\)：

#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #include<iostream> #include<queue> #define rg register using namespace std; inline int read(){rg int f=0,x=0;rg char ch=getchar();while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return f?-x:x; }const int N =25010; const int M =150010; const int inf =0x7f7f7f7f; int n,r,p,s,head[N],tot,dis[N]; bool vis[N]; struct edge{int to,nxt,w; }e[M]; inline void add(rg int u,rg int v,rg int w){e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot; } inline void spfa(rg int s){for(rg int i=1;i<=n;++i) dis[i]=inf;dis[s]=0;deque<int > q;q.push_back(s);while(!q.empty()){int u=q.front();q.pop_front();vis[u]=false;for(rg int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(dis[v]>dis[u]+e[i].w){dis[v]=dis[u]+e[i].w;if(!vis[v]){vis[v]=true;if(q.empty()||dis[v]>dis[q.front()]) q.push_back(v);else q.push_front(v);}}}}} signed main(){n=read(),r=read(),p=read(),s=read();for(rg int i=1;i<=r;++i){int u=read(),v=read(),w=read();add(u,v,w),add(v,u,w);}for(rg int i=1;i<=p;++i){int u=read(),v=read(),w=read();add(u,v,w);}spfa(s);for(rg int i=1;i<=n;++i)if(dis[i]==inf) printf("NO PATH\n");else printf("%d\n",dis[i]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/horrigue/p/9641636.html

總結(jié)

以上是生活随笔為你收集整理的「BZOJ2200」[Usaco2011 Jan] 道路和航线 - 最短路+拓扑排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。