HDU 1839 Delay Constrained Maximum Capacity Path 最短路+二分

题目来源:HDU 1839 Delay Constrained Maximum Capacity Path

题意:给你一张无向图 要从1到n运送东西 每条路都有容量限制和经过的时间 选择一条路径该路径最多能运的数量等于容量最少的那条边 并且总时间不能超过T

思路:和上一题一样 二分容量 然后做最短路判断是否最短时间小于等于T

#include #include #include #include using namespace std; const int maxn = 50010; struct edge { int u, v, h, w; }; struct HeapNode { int u, d; bool operator rhs.d; } }; vector G[maxn]; int dis[maxn]; bool vis[maxn]; int n, m, t; void Dijkstra(int h) { for(int i = 0; i Q; Q.push((HeapNode){1, 0}); while(!Q.empty()) { HeapNode x = Q.top(); Q.pop(); int u = x.u; if(vis[u]) continue; vis[u] = true; for(int i = 0; i x.d + e.w) { dis[v] = x.d + e.w; Q.push((HeapNode){v, dis[v]}); } } } } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d %d %d", &n, &m, &t); for(int i = 0; i > 1; Dijkstra(mid); if(dis[n]

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:The State Pattern 状态模式
下一篇:C++类的方法设计
相关文章
图文推荐

HDU 1839 Delay Constrained Maximum Capacity Path 最短路+二分
ZOJ 3640 Help Me
HDU 1839 Delay Constrained Maximum Capacity Path 最短路+二分
CF 518C(Anya and
HDU 1839 Delay Constrained Maximum Capacity Path 最短路+二分
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-02-27 人气:2
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.305 (s). 10 q(s)