题解：UVA12047 Highest Paid Toll

He_Jie · 2025-06-07 20:31:56 · 题解

Highest Paid Toll

翻译

给定一个有权重的有向图，包含 n 个点和 m 条边。在所有从 s 到 t 的路径中，如果路径的总权重不超过 p，求这些路径中经过的边的最大权重的最大可能值。如果不存在这样的路径，返回 -1。

解法

双向 Dijkstra（或结合正向和反向 Dijkstra 的方法）是解决这类带限制的最短路径问题的经典做法，尤其在需要同时考虑路径总权值和路径上某些边权值的极值（如最大边权值）时非常有效。

分别以 s 和 t（反图）为起点，用 Dijkstra 算法跑一遍，得到从 s 出发到其他点的最短距离 dist\_s 和从 t 出发到其他点的最短距离 dist\_t（在反图中）。遍历每一条边 u \to v，权值为 w，计算经过这条边的最短路径 dist\_s[u] + w + dist\_t[v]。
如果该最短路径不超过 p，则将该边的权值 w 纳入候选。
最终答案为所有候选边权值的最大值，若不存在则返回 -1。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

typedef long long ll;

void solve() {
    int n, m, s, t, p;
    cin >> n >> m >> s >> t >> p;

    vector<vector<pair<int, int> > > adj(n);

    int u, v, w;
    for (int i = 0; i < m; i ++) {
        cin >> u >> v >> w;
        u --, v --;
        adj[u].push_back(make_pair(v, w));
    }

    s --, t --;

    vector<vector<pair<int, int> > > adj1(n);

    for (int i = 0; i < n; i ++) {
        for (size_t j = 0; j < adj[i].size(); ++j) {
            int v = adj[i][j].first;
            int w = adj[i][j].second;
            adj1[v].push_back(make_pair(i, w));
        }
    }

    vector<int> dist_s(n, -1), dist_t(n, -1);

    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

    pq.push(make_pair(0, s));

    while (!pq.empty()) {
        pair<int, int> top = pq.top();
        pq.pop();
        int d = top.first;
        int u = top.second;
        if (dist_s[u] != -1) continue;
        dist_s[u] = d;
        for (size_t j = 0; j < adj[u].size(); ++j) {
            int v = adj[u][j].first;
            int w = adj[u][j].second;
            if (dist_s[v] != -1) continue;
            pq.push(make_pair(d + w, v));
        }
    }

    pq.push(make_pair(0, t));

    while (!pq.empty()) {
        pair<int, int> top = pq.top();
        pq.pop();
        int d = top.first;
        int u = top.second;
        if (dist_t[u] != -1) continue;
        dist_t[u] = d;
        for (size_t j = 0; j < adj1[u].size(); ++j) {
            int v = adj1[u][j].first;
            int w = adj1[u][j].second;
            if (dist_t[v] != -1) continue;
            pq.push(make_pair(d + w, v));
        }
    }

    int ans = -1;
    for (int u = 0; u < n; u ++) {
        for (size_t j = 0; j < adj[u].size(); ++j) {
            int v = adj[u][j].first;
            int w = adj[u][j].second;
            if (dist_s[u] != -1 && dist_t[v] != -1 && dist_s[u] + dist_t[v] + w <= p) {
                ans = max(ans, w);
            }
        }
    }

    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t --) {
        solve();
    }

    return 0;
}