题目链接:
http://acm.hdu.edu.cn/showPRoblem.php?pid=1839
题意:
有N个点，点1为珍贵矿物的采矿区， 点N为加工厂，有M条双向连通的边连接这些点。走每条边的运输容量为C，运送时间为D。
他们要选择一条从1到N的路径运输， 这条路径的运输总时间要在T之内，在这个前提之下，要让这条路径的运输容量尽可能地大。
一条路径的运输容量取决与这条路径中的运输容量最小的那条边。
题解:
二分cap，最短路判断
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//////////////////////////////////////////////////////////////////////////
const int maxn = 1e5+10;
int n,m,t;
ll c[maxn];
struct node{
ll v,c,d;
node(ll v=0,ll c=0,ll d=0) : v(v),c(c),d(d) {}
};
vector<node> E[maxn];
int inq[maxn],td[maxn];
ll check(ll c){
for(int i=0; i<=n; i++) inq[i] = 0;
for(int i=0; i<=n; i++) td[i] = INF;
queue<int> q;
q.push(1),td[1]=0,inq[1]=1;
while(!q.empty()){
int now = q.front();
q.pop(),inq[now]=0;
for(int i=0; i<(int)E[now].size(); i++){
node e = E[now][i];
ll v = e.v, cc = e.c, d = e.d;
if(td[v] > td[now]+d && cc >= c){
td[v] = td[now]+d;
if(inq[v]) continue;
inq[v] = 1;
q.push(v);
}
}
}
return td[n];
}
int main(){
int T = read();
while(T--){
scanf("%d%d%d",&n,&m,&t);
for(int i=0; i<=n; i++) E[i].clear();
MS(c);
for(int i=0; i<m; i++){
ll u,v,d; scanf("%I64d%I64d%I64d%I64d",&u,&v,&c[i],&d);
E[u].push_back(node{v,c[i],d});
E[v].push_back(node{u,c[i],d});
}
sort(c,c+m);
int l=0,r=m-1,ans;
while(l<=r){
int mid = (l+r)/2;
int tmp = c[mid];
if(check(tmp) <= t){
ans = tmp;
l = mid+1;
}else{
r = mid-1;
}
}
cout << ans << endl;
}
return 0;
}
