运输货物

问题描述

考虑一个具有N个顶点，M条边的无向图。编号为1的顶点对应于一个矿山，从中提取一些珍贵的矿物。编号为N的顶点对应于一家矿物加工厂。每条边连接两个不同的顶点并拥有有两个参数，分别为最大承重量C和通行时间D。现在将从矿山中提取的矿物并选择一条路径将提取的矿物运送至工厂。该路径应具有最大的承重量，以便能够同时运输尽可能多的矿物。路径的承重量等于路径中经过的边的最大承重量的最小值。但是，这些矿物非常敏感，一旦从矿山中提取出来，它们将在T时间单位后开始分解，除非他们在此时间间隔内到达工厂。因此，所选路径的总行进时间（其路径的通行时间之和）应小于或等于T。

输入格式

输入的第一行包含一个整数X，表示测试用例的数量。
每个测试用例的第一行包含3个整数，并用空格分隔：N，M，T。接下来的M行中的每行将包含四个整数，每个数字用空格分隔：A，B，C和D，这意味着顶点A和B之间存在一条边，最大承重量为C，通行时间为D。A和B是1和N之间的不同整数。任何两个顶点之间最多存在一个边。

输出格式

对于X个测试用例，请输出在满足通行时间限制下的路径最大承重量，每个测试用例对应一行。
数据保证图中至少存在一条1到n通行总时间小于等于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

数据规模和约定

1≤𝑛≤10000， 1≤m≤50000，1≤𝑇≤500000
1≤𝐶≤10000000， 1≤𝐷≤50000

#include <bits/stdc++.h>
using namespace std;

int x, n, m, t, a, b, c, d, minC, dis[2000005], vis[2000005], head[2000005];
int tot = 0;  // 当前边的总数
struct edge {
    int u, v, next, c, d;
} edges[2000005];

void addEdge(int u, int v, int c, int d) {  // 加一条边
    edges[tot].u = u, edges[tot].v = v, edges[tot].next = head[u], edges[tot].c = c, edges[tot].d = d;
    head[u] = tot++;
}

bool spfa(int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    dis[s] = 0;
    q.emplace(s);
    vis[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i != -1; i = edges[i].next) {
            if (edges[i].c < minC)
                continue;
            int &v = edges[i].v, newdis = dis[u] + edges[i].d, &disv = dis[v];
            if (disv > newdis) {
                disv = newdis;
                if (!vis[v]) {
                    vis[v] = 1;
                    q.emplace(v);
                }
            }
        }
    }
    return dis[n] <= t;
}

int main() {
    scanf("%d", &x);
    for (int i = 0; i < x; i++) {
        memset(head, -1, sizeof(head));  // 储存每个节点的第一条边的编号，-1表示没有边
        tot = 0;
        scanf("%d%d%d", &n, &m, &t);
        for (int j = 0; j < m; j++) {
            scanf("%d%d%d%d", &a, &b, &c, &d);
            addEdge(a, b, c, d);
            addEdge(b, a, c, d);
        }
        int l = 0, r = 30000000;
        while (l < r) {
            minC = (l + r) / 2;
            if (spfa(1))
                l = minC + 1;
            else
                r = minC;
        }
        printf("%d\n", l - 1);
    }
    return 0;
}