HDU 1839

http://acm.hdu.edu.cn/showproblem.php?pid=1839

题意：从1到n，要求时间小于等于T到达。每条边有一个容量，问最多能运多少货物。

分析：最多能运的货物取决于路径上边的最小容量，所以二分容量，再用最短路判断时限即可。最短路里面多加一个判断保证走的边都能满足当前容量

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int INF=0xfffffff;

struct Edge {
    int s, t, v, cap, nxt;
}e[200005]; 

int n, m, T, cnt, minn, head[10005], dis[10005], vis[10005];

void add(int s, int t, int v, int cap) {
    e[cnt].t = t, e[cnt].v = v, e[cnt].cap = cap, e[cnt].nxt = head[s], head[s] = cnt++;
}

void INIT() {
    cnt = 0;
    memset(head, -1, sizeof(head));
}

void spfa(int s) {
    for(int i = 1; i <= n; i++) dis[i] = INF;
    dis[s] = 0;
    memset(vis, 0, sizeof(vis));
    queue <int> q;
    q.push(s);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = head[u]; i != -1; i = e[i].nxt) {
            if(e[i].cap >= minn) {
                int t = e[i].t;
                if(dis[t] > dis[u] + e[i].v) {
                    dis[t] = dis[u] + e[i].v;
                    if(!vis[t]) {
                        vis[t] = 1;
                        q.push(t);
                    }
                }
            }
        }
    }
}

int main() {
    int cas;
    scanf("%d", &cas);
    while(cas--) {
        INIT();
        scanf("%d%d%d", &n, &m, &T);
        for(int i = 0; i < m; i++) {
            int s, t, c, d;
            scanf("%d%d%d%d", &s, &t, &c, &d);
            add(s, t, d, c), add(t, s, d, c);
        }
        int L, R;
        L = 1, R = 2000000000;
        while(L < R) {
            minn = (L + R) / 2;
            spfa(1);
            if(dis[n] > T) R = minn;
            else L = minn + 1;
        }
        printf("%d
", L - 1);
    }
    return 0;
}