題目大意：
有N個城市，編號1-N
有R條路，每條路（單向）的起點為Si，終點為Di，長度為Li，如果要走這條路需要花Ti的錢
現在你只有K元錢，求在不超支的前提下，從1走到N需要的最短距離

?

這里總是希望路程盡可能的短，那么利用dijkstra的方法來解決問題，總是先擴展距離近的點，這樣能更快的找到終點的最短路

節點的擴展滿足二維的情況，只要路程和費用兩個限制條件中的其中一個滿足情況那么當前節點便要擴展

?

用cost[i],dis[i]記錄在i節點所能達到的最優狀態，只有某個情況left>cost[v] && d<dis[i]?那么兩維情況都滿足條件，就可以更新cost[],dis[]

但是這里要注意的是 dis[n]并不一定是最終答案，因為可能路程最短并不一定花費最少，那么就不會去更新這兩個數組，我們只要把第一個帶n的從

優先隊列中跳出的點的長度作為答案即可，因為是優先隊列，所以先彈出的n的點，一定是距離最短的

?

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <queue> 5 using namespace std; 6 #define N 10010 7 #define MAXN 200010 8 #define ll long long 9 const int INF = 0x3f3f3f3f; 10 11 int k,n,m; 12 int dis[N] , cost[N]; 13 int first[N] , kk; 14 15 struct Edge{ 16 int x , y , next , d , c; 17 Edge(int x=0 , int y=0 , int next=0 , int d=0 , int c=0):x(x),y(y),next(next),d(d),c(c){} 18 }e[N<<1]; 19 20 struct City{ 21 int id , d , money; 22 City(int id , int d=0 , int money=0):id(id),d(d),money(money){} 23 bool operator<(const City &m) const { 24 if(d == m.d) return money<m.money; 25 else return d>m.d; 26 } 27 }; 28 29 priority_queue<City> q; 30 31 void add_edge(int x,int y,int d,int c) 32 { 33 e[kk] = Edge(x,y,first[x],d,c); 34 first[x]=kk++; 35 } 36 37 int dijkstra() 38 { 39 while(!q.empty()) q.pop(); 40 memset(dis , 0x3f , sizeof(dis)); 41 memset(cost , -1 , sizeof(cost)); 42 q.push(City(1 , 0 , k)); 43 dis[1] = 0 , cost[1] = k; 44 while(!q.empty()) 45 { 46 City u = q.top(); 47 q.pop(); 48 if(u.id == n) return u.d; 49 if(u.d>dis[u.id] && u.money<cost[u.id]) continue; 50 for(int i = first[u.id] ; ~i ; i=e[i].next){ 51 int v = e[i].y; 52 if(u.money-e[i].c>=0 && (u.money-e[i].c>cost[v] || u.d+e[i].d<dis[v])){ 53 int left = u.money-e[i].c; 54 int distance = u.d+e[i].d; 55 q.push(City(v,distance,left)); 56 if(left>cost[v] && distance<dis[v]){ 57 cost[v] = left; 58 dis[v] = distance; 59 } 60 } 61 } 62 } 63 return INF; 64 } 65 66 int main() 67 { 68 // freopen("a.in" , "r" , stdin); 69 while(~scanf("%d%d%d", &k , &n , &m)) 70 { 71 kk=0; 72 memset(first , -1 , sizeof(first)); 73 for(int i=0 ; i<m ; i++){ 74 int x,y,d,c; 75 scanf("%d%d%d%d" , &x , &y , &d , &c); 76 add_edge(x , y , d , c); 77 } 78 int ans = dijkstra(); 79 if(ans == INF) puts("-1"); 80 else printf("%d\n" , ans); 81 } 82 return 0; 83 }

?

轉載于:https://www.cnblogs.com/CSU3901130321/p/4504625.html

總結

以上是生活随笔為你收集整理的POJ 1724 二维费用最短路的全部內容，希望文章能夠幫你解決所遇到的問題。

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