UVa1265 - Flying to Fredericton(Dijkstra)

題目大意

Brett 現在人在 Calgary 他想要透過飛機到 Fredericton，他想要走最省錢的方式抵達，他可以忍受 x 次轉機
請告訴 Brett 他最多忍受幾次轉機，最省錢抵達 Fredericton 的成本是多少

題目連結

重點觀念

• dijkstra’s by 大衛的筆記
• dijkstra 增加一維度，紀錄轉機次數
• 最多忍受，但不一定要剛好忍受 x 次班機，如果 x-2 次有更好的答案，為何不用呢?
• 題目有嚴格輸出

分析

• 題目的城市進行簡單 hash
• 使用 dijkstra 並記錄，成本多少、轉機幾次，以成本最少為 priority queue
• dijkstra 增加一維度，記錄轉機次數
  如果 x 點轉機三次，則是 dist[x][3]
• 用一個迴圈，讓一些轉機次數比較少，但成本低的，可以取代轉機次數高，且成本也高
  • 如果轉機次數多，成本高，那就不需要那麼多次轉機了
  • 題目說的是容忍最多 x 次轉機
• 由於城市最多只會有 100 個，因此當轉機次數大於 100 時，基本上是不可能的，直接當作是 100 即可。

參考連結

UVA 11280 - Flying to Fredericton（最短路） by lab104_yifan

題目程式碼

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

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 120
#define INF 0x3f3f3f3f
//#define int long long
using namespace std;
int t, n, m, kase=1;
int q, step; //q 查詢, step 轉機最多幾次
int a, b, c, int_city; 
string city, cityA, cityB; //用來輸入 city 
map<string, int> citys; //hash citys 
int dist[MAXN][MAXN]; //dist[city_name][int_city] 分析 3

struct status{ // 我們使用 Edge struct 實做 (root, cost)
    int v, c, step; //step 轉機幾次
    status(): v(0), c(0), step(0) {}
    status(int _v, int _c, int _step): v(_v), c(_c), step(_step) {}

    bool operator < (const status& other) const{
        return c < other.c; //遞減排序，決定 priority_queue 的方式
        //return c > other.c; //遞增排序
    }
};

struct Edge{ // 我們使用 Edge struct 實做 (root, cost)
    int v, c;
    Edge(): v(0), c(0){}
    Edge(int _v, int _c): v(_v), c(_c){}

    bool operator < (const Edge& other) const{
        return c < other.c; //遞減排序，決定 priority_queue 的方式
        //return c > other.c; //遞增排序
    }
};
vector<Edge> edge[MAXN]; //放入題目的邊

void dijkstra(int root){
    deque<status> q; 
    q.push_back({root,0,0}); //初始放入開始點
    memset(dist, 0x3f, sizeof(dist)); //全部 dist 無限大
    dist[root][0] = 0; //自己到自己成本為零
    int cost;
    while(!q.empty()){
        status node = q.front(); q.pop_front();
        //cout << node.v << " " << node.c << "\n";
        if(node.step > 110) continue; //轉機 110 次以上基本上不合法
        for(auto it: edge[node.v]){ 
            cost = dist[node.v][node.step] + it.c; //分析 3
            //node.step+1 要比轉機後的成本還要低，才有取代的價值
            if(cost < dist[it.v][node.step+1]){ 
                q.push_back({it.v, cost, node.step+1}); //放入資料
                dist[it.v][node.step+1] = cost; //更改成本
            }
        }
    }
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL

    cin >> t;
    while(t--){
        int_city = 0;
        citys.clear();
        cin >> n;
        for(int i = 0; i < n; i++){
            cin >> city;
            citys[city] = int_city++; //hash city 
            edge[i].clear(); //資料清除
        }
        cin >> m;
        for(int i = 0; i < m; i++){
            cin >> cityA >> cityB >> c;
            edge[citys[cityA]].push_back({citys[cityB], c}); //加入有向邊
            //cout << citys[cityA] << " " << citys[cityB] << " " << c << "\n";
        }
        dijkstra(citys["Calgary"]); //從起點出發
        cout << "Scenario #" << kase++ << "\n";
        cin >> q;

        for(int i = 1; i < MAXN; i++){ //分析 4
           dist[citys["Fredericton"]][i] = min(dist[citys["Fredericton"]][i], dist[citys["Fredericton"]][i-1]);
        }
        int ans;
        for(int i = 0; i < q; i++){
            cin >> step;
            if(step > 100) step = 100; //分析 5
            ans = dist[citys["Fredericton"]][step+1]; 

            if(ans == INF) cout << "No satisfactory flights\n";
            else cout << "Total cost of flight(s) is $" << ans << "\n";
        }
        if(t != 0) cout << "\n";
    }
    return 0;
}