题目描述

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

样例

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

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1000010;
ll n,m,time1,dist[N];
ll h[N],e[N],ne[N],idx,w[N],v[N];
bool st[N];
queue<int>q;

void add(int a,int b,int c,int d)
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,v[idx] = d,h[a] = idx++;
}

ll check(int x)
{
    for(int i = 1;i <= n;i++)
    {
        dist[i] = 1e18;
    }
    memset(st,0,sizeof st);
    while(!q.empty())
    {
        q.pop();
    }
    q.push(1);
    st[1] = true;
    dist[1] = 0;
    while(q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i];
            if(v[i] >= x && dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return dist[n];
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset(h,-1,sizeof h);
        memset(e,0,sizeof e);
        memset(ne,0,sizeof ne);
        ll top = -1,lower = 1e18;
        cin >> n >> m >> time1;
        while(m--)
        {
            ll a,b,c,d;
            cin >> a >> b >> c >> d;
            add(a,b,d,c),add(b,a,d,c);
            top = max(top,c),lower = min(lower,c);
        }
        ll ans = 0;
        while(lower <= top)
        {
            int mid = lower + top >> 1;
            if(check(mid) == time1)
            {
                ans = mid;
                break;
            }
            else if(check(mid) < time1)
            {
                lower = mid + 1;
            }
            else if(check(mid) > time1)
            {
                top = mid - 1;
            }
        }
        cout << check(99) << endl;
    }
}