题干：

考虑一个包含 N 个顶点的无向图，编号从 1 到 N，并包含 M 条边。编号为 1 的顶点对应了一个矿藏，可从中提取珍稀的矿石。编号为 N 的顶点对应了一个矿石加工厂。每条边有相应的通行时间 (以时间单位计)，以及相应的运载量 (以矿石单位计)。现决定使用一条路径，将从矿藏中提取的矿石运送到加工厂。这条路径应当具有尽可能高的运载量，以便并行运输尽可能多的矿石。路径的运载量等于它的各边的最小运载量。然而，这些矿石很敏感，一旦从矿藏中提取出来，就会在 T 个时间单位之后开始分解，除非在这个时间截止之前到达工厂。因此，所选路径的总通行时间 (各条边的通行时间之和) 应当小于或等于 T。

输入

输入的第 1 行包含一个整数 X，表示测试数据的组数。

对于每组测试数据，第 1 行包含了以空格分隔的三个整数：N (2 ≤ N ≤ 10000)，M (1 ≤ M ≤ 50000) 和 T (1 ≤ T ≤ 500000)。接下来的 M 行，每行包含以空格分隔的四个整数：A, B, C, D，表示顶点 A 和 B 之间有一条边，边的运载量是 C (1 ≤ C ≤ 2×10^9)，边的通行时间是 D (1 ≤ D ≤ 50000)。A 和 B 是介于 1 到 N 之间的不同整数。任意两个顶点之间，至多有一条边。

输出

对于每组测试数据，在一行里输出从矿藏到工厂的路径的最大运载量，考虑到通行时间的约束。在满足通行时间约束的条件下，矿藏和工厂之间总是存在至少一条路径。

示例输入

2
2 1 10
1 2 13 10
4 4 20
1 2 1000 15
2 4 999 6
1 3 100 15
3 4 99 4

示例输出

13
99

解题报告：

  题目不难，给定一个T，求起点到终点的在时间T内的 能够装载的最大矿石。二分这个装载数+最短路check就行了。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
const int INF = 0x3f3f3f3f;
struct Edge {
	int to,ne,w,zzl;//装载量 
} e[MAX];
int tot,n,m,T;
int head[MAX],dis[MAX],vis[MAX];
struct Point {
	int pos;
	int c;
	Point(){}
	Point(int pos,int c):pos(pos),c(c){}
	bool operator<(const Point b)const{
		return c > b.c;
	}
};
void add(int u,int v,int w,int zzl) {
	e[++tot].to = v;
	e[tot].w = w;
	e[tot].zzl=zzl;
	e[tot].ne = head[u];
	head[u] = tot;
}
int Dijkstra(int x) {
	for(int i = 1; i<=n; i++) dis[i] = INF,vis[i] = 0;
	dis[1]=0;
	priority_queue<Point> pq;
	pq.push(Point(1,0));
	while(!pq.empty()) {
		Point cur = pq.top();pq.pop();
		if(vis[cur.pos]) continue;
		vis[cur.pos] = 1;
		for(int i = head[cur.pos]; ~i; i = e[i].ne) {
			int v = e[i].to;
			if(vis[v]) continue;
			if(e[i].zzl < x) continue;
			if(dis[v] > dis[cur.pos] + e[i].w) {
				dis[v] = dis[cur.pos] + e[i].w;
				pq.push(Point(v,dis[v]));
			}
		}
	}
	return dis[n];
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		scanf("%d%d%d",&n,&m,&T);
		tot=0;
		int l = INF,r = 0,mid,ans;
		for(int i = 1; i<=n; i++) head[i] = -1;
		for(int a,b,c,d,i = 1; i<=m; i++) {
			scanf("%d%d%d%d",&a,&b,&c,&d);
			add(a,b,d,c);
			add(b,a,d,c);
			r = max(r,c);
			l = min(l,c);
		}
		while(l<=r) {
			mid = (l+r)>>1;
			if(Dijkstra(mid) <= T) ans = mid,l = mid+1;
			else r = mid-1;			
		}
		printf("%d\n",ans);
	}
	return 0 ;
}