POJ|POJ 1724 二维费用最短路
题目大意:
有N个城市,编号1-N
有R条路,每条路(单向)的起点为Si,终点为Di,长度为Li,如果要走这条路需要花Ti的钱
现在你只有K元钱,求在不超支的前提下,从1走到N需要的最短距离
这里总是希望路程尽可能的短,那么利用dijkstra的方法来解决问题,总是先扩展距离近的点,这样能更快的找到终点的最短路
【POJ|POJ 1724 二维费用最短路】节点的扩展满足二维的情况,只要路程和费用两个限制条件中的其中一个满足情况那么当前节点便要扩展
用cost[i],dis[i]记录在i节点所能达到的最优状态,只有某个情况left>cost[v] && d
优先队列中跳出的点的长度作为答案即可,因为是优先队列,所以先弹出的n的点,一定是距离最短的
1 #include2 #include 3 #include 4 #include 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{ 16int x , y , next , d , c; 17Edge(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{ 21int id , d , money; 22City(int id , int d=0 , int money=0):id(id),d(d),money(money){} 23bool operator<(const City &m) const { 24if(d == m.d) return money m.d; 26} 27 }; 28 29 priority_queue q; 30 31 void add_edge(int x,int y,int d,int c) 32 { 33e[kk] = Edge(x,y,first[x],d,c); 34first[x]=kk++; 35 } 36 37 int dijkstra() 38 { 39while(!q.empty()) q.pop(); 40memset(dis , 0x3f , sizeof(dis)); 41memset(cost , -1 , sizeof(cost)); 42q.push(City(1 , 0 , k)); 43dis[1] = 0 , cost[1] = k; 44while(!q.empty()) 45{ 46City u = q.top(); 47q.pop(); 48if(u.id == n) return u.d; 49if(u.d>dis[u.id] && u.money =0 && (u.money-e[i].c>cost[v] || u.d+e[i].d cost[v] && distance
转载于:https://www.cnblogs.com/CSU3901130321/p/4504625.html
推荐阅读
- 分享!如何分分钟实现微信扫二维码调用外部浏览器打开指定页面的功能
- 20180531去二维火学习完给股东的分享
- Spring|Spring 框架之 AOP 原理剖析已经出炉!!!预定的童鞋可以识别下发二维码去看了
- Vue+jszip+file-saver|Vue+jszip+file-saver 实现el-table中qrcode生成的二维码图片批量打包成zip下载
- 给定一个|给定一个 n × n 的二维矩阵表示一个图像, 将图像顺时针旋转 90 度js实现
- iOS|iOS 原生扫码二维码与自定义相机
- 动态创建二维数组
- Leetcode|Leetcode 算法题解系列 - 二维数组快速查找元素(二叉搜索树)
- AntD+jsQr做一个简单的前端二维码识别
- vue项目中生成qr码