Description
農場主John最近在網上買了一輛新車，在購買汽車配件時，John不小心點了兩次“提交”按鈕。導致汽車上安裝了兩套GPS系統，更糟糕的是John在使用GPS導航時，兩套系統常常給出不同的路線。從地圖上看，John居住的地區有N個十字路口和M條限定通行方向的道路。第i條道路連接路口A_i(1≤A_i≤N)和B_i(1≤B_i≤N)，兩個路口之間可能連接有多條道路。允許雙向通?的道路是將兩條單向通?的道路隔開所形成的。 John的家在路口1位置，農場在路口N的位置。John可以沿著?系列單向道路從家駕車到農場。所有GPS系統的底層地圖信息都是?樣的，區別僅在于對每一條道路的通?時間計算不同。對于第i條道路第一套GPS系統計算通行時間為P_i個單位時間，而第二套GPS系統則給出Q_i個單位時間。（所有道路的通行時間都是范圍在1到100，000之間的整數）John想要駕車從家到農場。可是，一路上GPS系統總是不厭其煩的提醒John（請從路口X開往路口Y），這是由于John選取了某套GPS系統建議的路徑，而另一套GPS系統則認為這不是從路口X到農場的最短路徑。我們稱之為GPS系統的抱怨。 請你計算一下如果John選擇合適的路徑到達農場能聽到的最少GPS系統的抱怨數 。如果John經過某條道路兩套GPS系統都發出抱怨，則抱怨總數加2。
Input
第一行，兩個整數N和M。接下來M行，其中第i行描述了道路i的信息，A_i B_i P_i Q_i。
Output
一個整數，表示John一路上能聽到的最小抱怨數。
Hint
2≤N≤100000，1≤M≤500000。
Solution
洛谷上面的題都坑爹得一批，指針也坑爹得一批，然后這道題成功地兩條都應驗了。。。
呃這道題首先是個最短路然后要建三張圖跑三次，Dijkstra和SPFA好像都可以不過為了復習SPFA我還是寫的SPFA即使它非常地坑人。。嗯然后兩個GPS的最短路徑各跑一遍，然后用一個for循環預處理出第三個圖的邊權，也就是這個聽抱怨的圖的邊權，然后只要他沒有聽GPS1或者2的都要++，都沒聽就會++兩次，然后最后再跑一次SPFA就可以了。
注意事項： 1.指針不能sizeof我要是再被這個坑了我就去自殺一百遍。。。 2.這個因為最后到的是n所以既然是單源最短路徑就要從n開始，而且，而且，而且，要，建，反圖。 3.好的我還是傻逼還是非常地弱，沒了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#define maxn 500005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,node1,x,y,z1,z2,node2,node3;
struct Edge{int u;int v;int w;int next;
}edge1[maxn],edge2[maxn],edge3[maxn];
int first1[maxn],last1[maxn],first2[maxn];
int last2[maxn],first3[maxn],last3[maxn];
int dist1[maxn],dist2[maxn],dist3[maxn];
bool vis1[maxn],vis2[maxn],vis3[maxn];
void addedge1(int u,int v,int w){edge1[++node1]=(Edge){u,v,w,0};if(first1[u]==0)first1[u]=node1;else edge1[last1[u]].next=node1;last1[u]=node1;
}
void addedge2(int u,int v,int w){edge2[++node2]=(Edge){u,v,w,0};if(first2[u]==0)first2[u]=node2;else edge2[last2[u]].next=node2;last2[u]=node2;
}
void addedge3(int u,int v,int w){edge3[++node3]=(Edge){u,v,w,0};if(first3[u]==0)first3[u]=node3;else edge3[last3[u]].next=node3;last3[u]=node3;
}
void init(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d%d",&x,&y,&z1,&z2);addedge1(y,x,z1);addedge2(y,x,z2);addedge3(y,x,0);}
}
void spfa1(int s,int *d){queue<int>pq;memset(d,inf,sizeof(dist1));d[s]=0;vis1[s]=true;pq.push(s);while(!pq.empty()){int u=pq.front();pq.pop();vis1[u]=false;for(int k=first1[u];k;k=edge1[k].next){int v=edge1[k].v;if(d[u]+edge1[k].w<=d[v]){d[v]=d[u]+edge1[k].w;if(!vis1[v]){vis1[v]=true;pq.push(v);}}}}
}
void spfa2(int s,int *d){queue<int>pq;memset(d,inf,sizeof(dist2));d[s]=0;vis2[s]=true;pq.push(s);while(!pq.empty()){int u=pq.front();pq.pop();vis2[u]=false;for(int k=first2[u];k;k=edge2[k].next){int v=edge2[k].v;if(d[u]+edge2[k].w<=d[v]){d[v]=d[u]+edge2[k].w;if(!vis2[v]){vis2[v]=true;pq.push(v);}}}}
}
void spfa3(int s,int *d){queue<int>pq;memset(d,inf,sizeof(dist3));d[s]=0;vis3[s]=true;pq.push(s);while(!pq.empty()){int u=pq.front();pq.pop();vis3[u]=false;for(int k=first3[u];k;k=edge3[k].next){int v=edge3[k].v;if(d[u]+edge3[k].w<=d[v]){d[v]=d[u]+edge3[k].w;if(!vis3[v]){vis3[v]=true;pq.push(v);}}}}
}
int main(){init();spfa1(n,dist1);spfa2(n,dist2);for(int i=1;i<=n;i++){for(int k=first3[i];k;k=edge3[k].next){int u=edge3[k].v;if(dist1[i]+edge1[k].w!=dist1[u])edge3[k].w++;if(dist2[i]+edge2[k].w!=dist2[u])edge3[k].w++;}}spfa3(n,dist3);printf("%d\n",dist3[1]);return 0;
}
實現方法)
)
