前言

這是今天C組的題，閑得無聊做了一會，結果就對了233。這算是學了SPFA之后的第一次實戰了。反正其他C組題我也不想做了。好了現在bi~~（系統自動屏蔽）也在做這道題。
還有這道題的名字叫

正題

題目

一個有向圖，有兩個GPS，它們認為每條邊的長度不盡相同，如果你走的路有GPS認為這不是最短路，就會報警警告一次，如果兩個GPS都認為不是，那就會警告2次，要求警告次數最少。

---

Input

第一行，整數N 和M。
接下來M 行，第i 行有四個整數Ai,Bi, Pi,Qi 描述第i 條道路。

Output

輸出單獨一行一個整數——FJ 選擇從他家到達農場的最佳線路之后，路上收到的最小總警告數。

Sample Input

5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5

Sample Output

1

【樣例解釋】

輸入詳述：

這里有5 個路口和7 條有向道路。第一條道路從路口3 到路口4 連接兩個路口；第一GPS 認為這條路需要7 單位時間來通過，接著第二GPS 認為它只需1單位時間，諸如此類。

輸出詳述：

如果FJ 按照路線1->2->4->5 走，那么第一GPS 會在1->2 這條路上發出警告（它認為1->3 這條路更好）。然而，對于路線剩下的2->4->5，兩個GPS 都快樂地坐著FJ 的小車通過了，因為每個GPS 都以為這是2 到5 的最短路。

---

解題思路

首先我們要分別算出2個GPS的每個點到達終點的最小值，然后判斷如果前一個點的最短路+兩點之間的權值不等于后一個點的最短路，則這個GPS會認為這條路是錯的。為了方便我們把有向圖倒著存，然后SPFA搜3次。

---

代碼

#include<cstdio> #include<cstring> using namespace std; struct line{int first,last,l1,l2,next; };//鄰接表 line a[50001]; int f[10001],f2[10001],ff[10001],n,m,ls[10001],state[10001],tail,head,p,w; bool b[10001]; void spfaA() {memset(f,127/3,sizeof(f));//初始化tail=1;head=0;f[n]=0;state[1]=n;b[n]=true;//初始化do{head=(head+2)%n-1;//循環隊列p=ls[state[head]];//找邊while (p!=0){if (f[a[p].first]+a[p].l1<f[a[p].last])//松弛{f[a[p].last]=f[a[p].first]+a[p].l1;if (!b[a[p].last]){tail=(tail+2)%n-1;//入隊state[tail]=a[p].last;b[a[p].last]=true;}}p=a[p].next;//下一條}b[state[head]]=false;//解封}while (tail!=head); } void spfaB()//一樣的不解釋 {memset(f2,127/3,sizeof(f2));tail=1;head=0;f2[n]=0;state[1]=n;b[n]=true;do{head=(head+2)%n-1;p=ls[state[head]];while (p!=0){if (f2[a[p].first]+a[p].l2<f2[a[p].last]){f2[a[p].last]=f2[a[p].first]+a[p].l2;if (!b[a[p].last]){tail=(tail+2)%n-1;state[tail]=a[p].last;b[a[p].last]=true;}}p=a[p].next;}b[state[head]]=false;}while (tail!=head); } int check(int x)//判斷該條邊會有幾個GPS報錯 {int s=0;if (f[a[x].first]+a[x].l1!=f[a[x].last]) s++;//第一個GPSif (f2[a[x].first]+a[x].l2!=f2[a[x].last]) s++;//第二個GPSreturn s;//返回 } void spfa() {memset(ff,127/3,sizeof(ff));tail=1;head=0;ff[n]=0;state[1]=n;b[n]=true;do{head=(head+2)%n-1;p=ls[state[head]];while (p!=0){w=check(p);//代價if (ff[a[p].first]+w<ff[a[p].last]){ff[a[p].last]=ff[a[p].first]+w;if (!b[a[p].last]){tail=(tail+2)%n-1;state[tail]=a[p].last;b[a[p].last]=true;}}p=a[p].next;}b[state[head]]=false;}while (tail!=head);printf("%d",ff[1]);//輸出 } int main() {freopen("gpsdual.in","r",stdin);freopen("gpsdual.out","w",stdout);scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){scanf("%d%d%d%d",&a[i].last,&a[i].first,&a[i].l1,&a[i].l2);a[i].next=ls[a[i].first];ls[a[i].first]=i;} spfaA();spfaB();spfa(); }

---

好了現在bi~~（系統自動屏蔽）做完了道題。

總結

以上是生活随笔為你收集整理的【jzoj3734,Usaco2014Open银组】双导航(gpsdual)的全部內容，希望文章能夠幫你解決所遇到的問題。

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