[poj1724]Roads
- 2020 年 3 月 14 日
- 筆記
歡迎回來，這裡是做圖論已經做到瘋了的愛上了圖論的Darth Victor。沒錯今天又是圖論題，最近一直在刷圖論。
題目
Bob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away – to the city N. He wants to get there as quickly as possible, but he is short on cash.
We want to help Bob to find the shortest path from the city 1 to the city N that he can afford with the amount of money he has.
Input
The second line contains the integer N, 2 <= N <= 100, the total number of cities.
The third line contains the integer R, 1 <= R <= 10000, the total number of roads.
Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters :
- S is the source city, 1 <= S <= N
- D is the destination city, 1 <= D <= N
- L is the road length, 1 <= L <= 100
- T is the toll (expressed in the number of coins), 0 <= T <=100
Notice that different roads may have the same source and destination cities.
Output
If such path does not exist, only number -1 should be written to the output.
Sample Input
5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2
Sample Output
11
解說
沒錯這是一個英文題。現解釋一下題意。一個住在1號城市的男的由於某種原因和女朋友吵架決定徹底決裂並遠走高飛，走得越遠越好。由於只有N座城市他決定跑到N號城市。可惜的是他的經濟脈搏都掌握在女朋友手裡拿不回來所以他身上只剩幾文小錢。但是路是別人的開的你想走得要錢吧，於是給了一張圖，每條路有長度，有過路費，問你這位同志憑他身上的錢能不能從1號城市跑到N號城市？如果可以的話最多路程是多少？
輸入也大概就這樣，第一行是身上的錢，第二行是城市數，第三行是道路數，之後輸入每條路的信息。如果他能到N就輸出最短路的長度，否則輸出-1。
那麼可見，這個最短路有兩個限制條件，一個是資金，一個是路程，並且資金優先於路程，即在資金滿足的情況下再去找最短路。既然多了一個限制，那麼應該在跑最短路的時候加一個篩選條件即可。迪杰特斯拉算法是按邊依次鬆弛到每一個點的距離的算法，那麼它在這裡用起來就十分方便，因為我們在鬆弛和入隊時加上限制條件即可。但是難點就在於，這個限制條件應該怎麼加？最開始我想的是在新長度小於原長度的更新條件下再加一條：在新長度小於原長度且走到現在用的資金小於原來走到這裡的資金兩者都滿足時，才能更新，並且一旦累計資金超額也直接continue掉，這樣跑一遍完整的迪杰特斯拉時就能找到答案。
但是不對。
仔細想想，這不符合之前提到的資金優先於路程，而是把兩個條件當成了同等級的。在假如有兩條路可以到達一個點，一個資金少路程長，另一個花錢多路程短，但兩個資金都足以到達終點，那麼我的算法會選擇路程長的路，不符合要求，這顯然不可以。
再想一想別的辦法。記得怎麼優化迪杰特斯拉嗎？對，用優先隊列，這保證了每次我們取出來的邊都是目前最短的。那既然這樣我們應該就可以把路程限制去掉，一旦搜到終點就直接return，這樣的話因為我們每次取出來的邊都是最小的，就能保證我們第一次搜到終點時的路程是最小的。當然，在搜的時候也是要加限制的，即一旦累計資金超出限額就不能鬆弛，這樣的話我們就能保證到達時資金在限額內且路程最短。
代碼
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<iostream> 6 #include<queue> 7 #include<stack> 8 using namespace std; 9 const int maxn=100+5; 10 int head[maxn],tot,v,n,m; 11 struct edge{ 12 int len,to,next,money; 13 }e[10000+5]; 14 void Add(int from,int to,int len,int money){ 15 e[tot].money=money; 16 e[tot].len=len; 17 e[tot].next=head[from]; 18 e[tot].to=to; 19 head[from]=tot; 20 tot++; 21 } 22 struct node{ 23 int num,dis,time; 24 node(int x,int y,int z){ 25 num=x; 26 dis=y; 27 time=z; 28 } 29 bool operator<(const node &a) const{ 30 return dis>a.dis; 31 } 32 }; 33 int Dijs(){ 34 priority_queue<node> q; 35 q.push(node(1,0,0)); 36 while(!q.empty()){ 37 node p=q.top();q.pop(); 38 int k=p.num; 39 if(k==n){ 40 return p.dis; 41 } 42 for(int i=head[k];i;i=e[i].next){ 43 int to,len,u; 44 to=e[i].to; 45 len=p.dis+e[i].len; 46 u=p.time+e[i].money; 47 if(u<=v){ 48 q.push(node(to,len,u)); 49 continue; 50 } 51 } 52 } 53 return 0x3f3f3f3f; 54 } 55 int main(){ 56 tot=1; 57 scanf("%d%d%d",&v,&n,&m); 58 for(int i=1;i<=m;i++){ 59 int from,to,len,money; 60 scanf("%d%d%d%d",&from,&to,&len,&money); 61 Add(from,to,len,money); 62 } 63 int ans=Dijs(); 64 if(ans==0x3f3f3f3f) printf("-1"); 65 else printf("%d",ans); 66 }
View Code
幸甚至哉，歌以詠志。
