UVa12768 - Inspired Procrastination(Dijkstra)

題目大意

一個很嚴重的問題常困擾著大學生，那就是拖延XD，我們現在來看你人生中一系列的事件，有些事件你可能會拖延，有些事不會，反而會提前做，也許有的時候你可能會在幾個重複的事件繞阿繞。

我們想找出如果我們在人生中一系列的事件中不斷的拖延，最多可以拖延多少，如果可以拖延一輩子都不做，就輸出 Unlimited!
題目連結

重點觀念

• dijkstra’s by 大衛的筆記
• 繞圈圈的 dijkstra 如何解決

分析

• 首先寫一個 dijkstra
• priority_queue 除了原本的 u,v 再加入一個陣列 visit[index] = dist
  • 其中 visit 表示從起點到 index 距離為多少，一開始設定為 0。方便 C++ struct init
  • 每次 priority_queue.push() 時，都會更新 visit[index] = dist
• 當再次碰到 visit[index] 且不等於 0 時表示準備進入重複事件，此時我們要判斷
  • 如果進入重複事件時當前成本，有比原本的 visit[index] 成本高，表示只要不斷的走重複路徑，就可以把拖延變得無限大。就可以輸出 Unlimited!
  • 如果進入重複事件時當前成本，有比原本的 visit[index] 成本小，表示只要一直走重複路徑，就可以把每件事情都提前，就不會有拖延，因此會直接 pop 掉。
• 題目輸出不可能為負數，如果是負數，就直接乾脆不走就好。

心得

好久沒有自己一個人不看詳解去寫題目了XD，原本還很怕這題會不會解不開來，因為自己不夠強，雖然有學習過，但還是不會解出變化題，結果幸好還是讓我有解開來，鰻開心的！

有種自己好像學以致用的感覺，好像比之前又更進步一些些。

不過也要感謝 udebug 提供大量測資，讓我不用一直想我錯在哪裡..，可以不斷驗證

題目程式碼

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

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 120
#define INF 1100*1100
using namespace std;
struct Edge{ // 我們使用 Edge struct 實做 (root, cost)
    int v, c;
    Edge(): v(0), c(0) {}
};

struct status{
    int v, c, visit[MAXN];
    status(): v(0), c(0) {}
    status(int _v, int _c): v(_v), c(_c) {}
    status(int _v, int _c, int _visit[]){
        v = _v;
        c = _c;
        for(int i = 0; i < MAXN; i++) visit[i] = _visit[i]; //不斷將資料透過 byval 寫入
    }

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

int n, m;
int a, b, cost;
vector<status> edge[MAXN]; //放入題目的邊
int dist[MAXN]; //從 root 出發到 x 邊的最短距離

int dijkstra(int root){
    status node = status(root, 0);
    node.visit[root] = 0;
    priority_queue<status> q;
    q.push(node); //初始放入開始點
    dist[root] = 0; //自己到自己成本為零


    int cost;
    while(!q.empty()){
        status node = q.top(); q.pop();
        //cout << node.v << " " << node.c << "\n";
        for(auto it: edge[node.v]){
            cost = dist[node.v] + it.c; //分析 3
            //cout << cost << " " << dist[it.v] << " " << node.visit[it.v] << "\n";
            if(node.visit[it.v] != 0){ //分析 3
                if(cost > node.visit[it.v]) return 0;
                if(cost <= node.visit[it.v]) continue;
            }


            if(cost > dist[it.v]){
                node.visit[it.v] = cost; //status 經過此路徑，新增紀錄
                q.push({it.v, cost, node.visit}); //push 資料
                node.visit[it.v] = 0; //更新過了，再改回來，以免干擾後續資料
                dist[it.v] = cost;
            }
        }
    }
    return 1;
}


int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    int cnt = 1;
    while(cin >> n >> m && (n+m) != 0){
        //if(cnt == 44) cout << "question " << n << " " << m << "\n";
        cnt++;

        for(int i = 1; i <= n; i++){ //清除邊、重置距離
            edge[i].clear();
            dist[i] = -INF;
        }
        for(int i = 0; i < m; i++){ //加入邊
            cin >> a >> b >> cost;
            edge[a].push_back({b,cost}); //單向時使用
        }

        int Inf_check = dijkstra(1);
        if(Inf_check == 0) cout << "Unlimited!\n"; //如果 return 0 表示拖延無限大
        else{
            int ans = 0; //最小為零
            for(int i = 1; i <= n; i++){
                ans = max(ans, dist[i]); //找最大拖延
            }
            cout << ans << "\n";
        }
    }
    return 0;
}