题目来源：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 < (const HeapNode& rhs)const { return d > rhs.d; } }; vector G[maxn]; int dis[maxn]; bool vis[maxn]; int n, m, t; void Dijkstra(int h) { for(int i = 0; i <= n; i++) dis[i] = 999999999; //memset(dis, 0x7f, sizeof(dis)); dis[1] = 0; memset(vis, false, sizeof(vis)); priority_queue 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 < G[u].size(); i++) { edge e = G[u][i]; if(e.h < h) continue; int v = e.v; if(dis[v] > 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 <= n; i++) G[i].clear(); for(int i = 0; i < m; i++) { int u, v, h, w; scanf("%d %d %d %d", &u, &v, &h, &w); G[u].push_back((edge){u, v, h, w}); G[v].push_back((edge){v, u, h, w}); } int l = 0, r = 2000000000, ans = -1; while(l <= r) { int mid = (l + r) >> 1; Dijkstra(mid); if(dis[n] <= t) { ans = mid; l = mid + 1; } else { r = mid - 1; } } printf("%d\n", ans); } return 0; }