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 < (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;
}