POJ 1724 二维费用最短路

题目大意：
有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的点，一定是距离最短的

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <queue>

 using namespace std;

 #define N 10010

 #define MAXN 200010

 #define ll long long

 const int INF = 0x3f3f3f3f;

 int k,n,m;

 int dis[N] , cost[N];

 int first[N] , kk;

 struct Edge{

     int x , y , next , d , c;

     Edge(int x= , int y= , int next= , int d= , int c=):x(x),y(y),next(next),d(d),c(c){}

 }e[N<<];

 struct City{

     int id , d , money;

     City(int id , int d= , int money=):id(id),d(d),money(money){}

     bool operator<(const City &m) const {

         if(d == m.d) return money<m.money;

         else return d>m.d;

     }

 };

 priority_queue<City> q;

 void add_edge(int x,int y,int d,int c)

 {

     e[kk] = Edge(x,y,first[x],d,c);

     first[x]=kk++;

 }

 int dijkstra()

 {

     while(!q.empty()) q.pop();

     memset(dis , 0x3f , sizeof(dis));

     memset(cost , - , sizeof(cost));

     q.push(City( ,  , k));

     dis[] =  , cost[] = k;

     while(!q.empty())

     {

         City u = q.top();

         q.pop();

         if(u.id == n) return u.d;

         if(u.d>dis[u.id] && u.money<cost[u.id]) continue;

         for(int i = first[u.id] ; ~i ; i=e[i].next){

             int v = e[i].y;

             if(u.money-e[i].c>= && (u.money-e[i].c>cost[v] || u.d+e[i].d<dis[v])){

                 int left = u.money-e[i].c;

                 int distance = u.d+e[i].d;

                 q.push(City(v,distance,left));

                 if(left>cost[v] && distance<dis[v]){

                     cost[v] = left;

                     dis[v] = distance;

                 }

             }

         }

     }

     return INF;

 }

 int main()

 {

    // freopen("a.in" , "r" , stdin);

     while(~scanf("%d%d%d", &k , &n , &m))

     {

         kk=;

         memset(first , - , sizeof(first));

         for(int i= ; i<m ; i++){

             int x,y,d,c;

             scanf("%d%d%d%d" , &x , &y , &d , &c);

             add_edge(x , y , d , c);

         }

         int ans = dijkstra();

         if(ans == INF) puts("-1");

         else printf("%d\n" , ans);

     }

     return ;

 }

巴特西

POJ 1724 二维费用最短路

最新文章

热门文章