問題描述
農夫約翰正在針對一個新區域的牛奶配送合同進行研究。他打算分發牛奶到T個城鎮（標號為1…T），這些城鎮通過R條標號為（1…R）的道路和P條標號為（1…P）的航路相連。

每一條公路i或者航路i表示成連接城鎮Ai（1<=A_i<=T）和Bi（1<=Bi<=T）代價為Ci。每一條公路，Ci的范圍為0<=Ci<=10,000；由于奇怪的運營策略，每一條航路的Ci可能為負的，也就是-10,000<=Ci<=10,000。

每一條公路都是雙向的，正向和反向的花費是一樣的，都是非負的。

每一條航路都根據輸入的Ai和Bi進行從Ai->Bi的單向通行。實際上，如果現在有一條航路是從Ai到Bi的話，那么意味著肯定沒有通行方案從Bi回到Ai。

農夫約翰想把他那優良的牛奶從配送中心送到各個城鎮，當然希望代價越小越好，你可以幫助他嘛？配送中心位于城鎮S中（1<=S<=T）。

輸入格式
輸入的第一行包含四個用空格隔開的整數T，R，P，S。

接下來R行，描述公路信息，每行包含三個整數，分別表示Ai，Bi和Ci。

接下來P行，描述航路信息，每行包含三個整數，分別表示Ai，Bi和Ci。

輸出格式
輸出T行，分別表示從城鎮S到每個城市的最小花費，如果到不了的話輸出NO PATH。
樣例輸入
6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10
樣例輸出
NO PATH
NO PATH
5
0
-95
-100
數據規模與約定
對于20%的數據，T<=100，R<=500，P<=500；

對于30%的數據，R<=1000，R<=10000，P<=3000；

對于100%的數據，1<=T<=25000，1<=R<=50000，1<=P<=50000。
思路：
這本來是最短路的一道模板題，但是太扯淡了，弄了很久。
坑點：
①有負數邊，得用spfa。
②邊數特別大，所以得優化一下，我用的deque+快讀優化。
③空間不要開小了，開小了會超時。。

但是就算是這樣，在dotcpp網站上還是沒有過去，得分95。在藍橋杯官網的網站上以421ms過的。

代碼如下：

#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std;const int maxx=1e5+10; const int maxm=1e6+10; struct edge{int to,next,w; }e[maxx<<6]; int head[maxx<<6],dis[maxx],vis[maxx],num[maxx]; int n,r,p,s,tot;inline void init() {tot=0;memset(head,-1,sizeof(head)); } inline void add(int u,int v,int w) {e[tot].to=v,e[tot].next=head[u],e[tot].w=w,head[u]=tot++; } inline void spfa() {memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));memset(num,0,sizeof(num));dis[s]=0;vis[s]=1;deque<int> q;q.push_front(s);while(q.size()){int u=q.front();q.pop_front();vis[u]=0;for(int i=head[u];i!=-1;i=e[i].next){int to=e[i].to;if(dis[to]>dis[u]+e[i].w){dis[to]=dis[u]+e[i].w;if(vis[to]==0){vis[to]=1;if(q.empty())q.push_front(to);else{if(dis[to]>dis[q.front()]) q.push_back(to);else q.push_front(to);}}}}} } inline int read() {int s = 0, w = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();return s * w; } int main() {n=read(),r=read(),p=read(),s=read();init();int x,y,z;for(int i=1;i<=r;i++){x=read();y=read();z=read();add(x,y,z);add(y,x,z);}for(int i=1;i<=p;i++){x=read();y=read();z=read();add(x,y,z);}spfa();for(int i=1;i<=n;i++){if(dis[i]==inf) printf("NO PATH\n");else printf("%d\n",dis[i]);}return 0; }

（本來想用deque+LLL優化一下呢，結果優化還不如不優化。。可能LLL不適合這道題目吧。）
努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的[蓝桥杯]算法提高 道路和航路（spfa+deque+快读优化）的全部內容，希望文章能夠幫你解決所遇到的問題。

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