UVa12047 - Highest Paid Toll(Dijkstra's)

題目大意

在一個城市中，每一條道路都必須要收過路費。
其中會給你一個數值 p，你從出發點到終點不可以花超過 p 費用，並且在符合前面條件下，會產生 toll
toll: 在你走的路徑中，花費最多一次的過路費。
請你找出最大的 toll 是多少。

題目連結

重點觀念

• dijkstra’s by 大衛的筆記

分析

• 由於 toll 在你走的路徑中，花費最多一次的過路費。
• 題目是單向圖
• 因此我們可以做兩張圖，第一張圖與題目相同、第二章圖與題目相反，且兩張圖都做 dijkstra
  • 第一張圖的出發點，為題目的出發點，定義為 st_dist
  • 第二張圖的出發點，以題目的終點為出發點 ed_dist
  • 再來我們的 toll 任意枚舉每一條邊，u -> v
• 公式： \(st_dist[u] + ed_dist[v] + edge[v].cost \)
  • 從出發點到 u 點的最短距離 + 從終點到 v 點的最短距離 + (u -> v) 的成本，是不是有比 p 小。
  • 如果有，就看有沒有比當前答案大，有就替換。
• 由於題目的每一個過路費最大可能到 \(10^4\)，因此 INF 必須要開到 \(10^5 * 10^5 = 10^10\)

參考連結

UVa 12047 by Morris’s
UVa 12047 by yulonglong

題目程式碼

有一些程式碼註解在 dijkstra’s by 大衛的筆記 請供參考。

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 10020
#define int long long
#define INF 2100000000
using namespace std;
int t, n, m;
int st, ed, p;
int a, b, c;
struct Edge{
    int v, c; //vector, cost;
    Edge(): v(0), c(0) {}
    Edge(int _v, int _c): v(_v), c(_c) {}

    bool operator < (const Edge& other) const{
        return c > other.c;
    }
};

//st_edge 題目圖, ed_edge 反向圖
vector<Edge> st_edge[MAXN], ed_edge[MAXN]; 
//以 st_dist 題目圖最小距離, ed_edge 反向圖最小距離
int visit[MAXN], st_dist[MAXN], ed_dist[MAXN];

void dijkstra(int root, vector<Edge> edge[MAXN], int dist[MAXN] ){
    priority_queue<int, vector<int>, greater<int> > q;
    q.push(root); //這裡理應要使用 dijkstra by 大衛的筆記，
    //但是我認為題目 n 太小，queue 應該也做得到，試試看，結果過了 AC XD。
    dist[root] = 0; 

    int cost, x;
    while(!q.empty()){ 
        x = q.top(); q.pop(); 
        for(auto it: edge[x]){ 
            cost = dist[x] + it.c;
            if(cost < dist[it.v]){
                q.push(it.v);
                dist[it.v] = cost;
            }
        }
    }
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // LOCLA
    cin >> t;
    while(t--){
        cin >> n >> m >> st >> ed >> p;
        for(int i = 1; i <= n; i++){ //clear
            st_edge[i].clear();
            st_dist[i] = INF;
            ed_edge[i].clear();
            ed_dist[i] = INF;
        }
        for(int i = 0; i < m; i++){
            cin >> a >> b >> c;
            st_edge[a].push_back({b,c}); //題目圖
            ed_edge[b].push_back({a,c}); //反向圖
        }
        dijkstra(st, st_edge, st_dist); //題目圖 dijkstra
        dijkstra(ed, ed_edge, ed_dist); //題目圖 dijkstra

        //cout << "dist 2 " << st_dist[2] << "\n";
        int ans = -1, cost = 0; //ans 題目答案
        for(int i = 1; i <= n; i++){ //枚舉每一個邊
            for(auto it: st_edge[i]){
                cost = st_dist[i] + ed_dist[it.v] + it.c; //分析 4
                //cout << "cost i j " << i << " " << it.v << " " << cost << "\n";
                //cout << "cost formula " << st_dist[i] << " " << ed_dist[it.v] << " " << it.c << "\n";
                if(cost <= p){ 
                    ans = max(ans, it.c);
                }
            }
        }
        cout << ans << "\n";
    }
    return 0;
}