题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1839
题意是有n个点，m条边，每条边都有两个权值，一个是这条边的容量，一个是经过这条路所要花费的时间。现在要从1到n，问最短时间内的最大流量是多少。
这道题我们可以用二分去枚举流量，然后跑dij去判断这个容量是否超过了所有边中的容量的最小值就好了。写的时候把pop写成了top，找bug找了半天...
AC代码：
代码语言：javascript复制#include <bits/stdc .h>
#define maxn 20005
#define maxm 100005
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
int to,w,val,next;
bool operator < (const Node &a) const{
return a.w < w;
}
}Edge[maxm],Now,Next;
int head[maxm],num;
int T,n,m,t;
void init(){
memset(head,-1,sizeof(head));
num = 0;
}
void add(int u,int v,ll val,int w){
Edge[num].w = w;
Edge[num].val = val;
Edge[num].to = v;
Edge[num].next = head[u];
head[u] = num ;
}
bool dijkstra(ll val){
int dist[maxn];
bool vis[maxn];
memset(vis,false,sizeof(vis));
memset(dist,inf,sizeof(dist));
dist[1] = 0;
Now.to = 1;
priority_queue<Node> q;
q.push(Now);
while(!q.empty()){
Now = q.top();
q.pop();
int ans = Now.to;
if(vis[ans] == true) continue;
vis[ans] = true;
for(int i=head[ans];i!=-1;i=Edge[i].next){
int u = Edge[i].to;
if(val <= Edge[i].val && !vis[u] && dist[u] > dist[ans] Edge[i].w){
dist[u] = dist[ans] Edge[i].w;
Next.to = u;
Next.w = dist[u];
q.push(Next);
}
}
}
return dist[n] <= t;
}
int main()
{
scanf("%d",&T);
while(T--){
init();
ll mi = 2000000000, mx = 0;
scanf("%d%d%d",&n,&m,&t);
for(int i=0;i<m;i ){
int u,v,w;
ll val;
scanf("%d%d%lld%d",&u,&v,&val,&w);
add(u, v, val, w);
add(v, u, val, w);
mi = min(mi, val);
mx = max(mx, val);
}
ll ans = -1;
ll l = mi, r = mx, mid;
while(l <= r){
ll mid = (l r) >> 1;
if(dijkstra(mid)){
ans = mid;
l = mid 1;
}
else{
r = mid - 1;
}
}
printf("%lldn",ans);
}
return 0;
}
