UVa10342 - Always Late(Dijkstra's、SPFA、次短路徑)

題目大意

有一支隊伍比賽時都會遲到，因為他們都喜歡走第二短路徑，且他們允許重複經過相同的道路。
請告訴我們，他們走第二短路徑需要花多少時間。

題目連結

重點觀念

• dijkstra’s by 大衛的筆記
  將 priority_queue 改成一般的 deque 即可。
• 使用 visit[node] 避免 deque 裡面有相同的節點，卻有不同的成本，導致浪費時間
• 路徑可以重複，但不能來回走
• dist[node][第幾短路徑] 來得知第二短路徑，從 0 開始表示第一短

分析

• 由於這題可以重複經過路徑，如果用 priority_queue 會變成都 front 成本小的節點，所以有高機率 priority_queue 都還在 front 起點附近的路徑，導致 TLE。
• dist[node][第幾短路徑]
  • 當現在的 cost = dist[node][x] 表示現在這個節點跟第 x 短路徑成本相同，並不需要紀錄
  • cost != dist[node][0] && cost != dist[node][1] 表示與第一、第二最短路徑不同
  • 如果 cost < dist[it.v][1] 表示當前第二短路徑還比較大，因此替換
  • if(cost < dist[it.v][0]) 表示當前第一短路徑還比成本高，因此把第一路徑和第二路徑成本替換，不需要跟 cost 換，因為會在上一個 if 就讓 cost != dist[node][0]
  • 紀錄現在 deque 裡面的節點有哪些，避免無線輪迴
    • 舉例有一個地圖是 (a,b)，沒有紀錄 deque 裡面節點則會導致，deque 不斷的進行 a,b

參考連結

[UVa] 10342 - Always Late by Hi, I am Code

心得

好題好題，我學起來了，有時候還是不太懂變形題，還要再多磨練

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 120
#define INF 2100000000
using namespace std;
struct Edge{ // 我們使用 Edge struct 實做 (root, cost)
    int v, c;
    Edge(): v(0), c(0) {}
    Edge(int _v, int _c): v(_v), c(_c) {}
};
struct Status{ // 我們使用 Status struct 實做 priority_queue (root, cost)
    int v, c; //v 節點, c 成本
    Status(): v(0), c(0) {}
    Status(int _v, int _c): v(_v), c(_c) {}

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

int kase = 1;
int n, r, q, start, destination;
int a, b, c;
vector<Edge> edge[MAXN];
int dist[MAXN][2];
int visit[MAXN];

void dijkstra(int root){
    //because dijkstra find second shortest path,which push duplicate node
    //priority_queue<Status> q; //TLE
    deque<Status> q;
    q.push_back({root,0}); //初始放入開始點
    dist[root][0] = 0; //自己到自己成本為零

    int cost;
    while(!q.empty()){
        Status node = q.front(); q.pop_front();
        //cout << node.v << " " << node.c << "\n";

        visit[node.v] = 0; //分析 2-5 可以再次經過他，因為不會使 deque 節點中資料在裡面 circle
        for(auto it: edge[node.v]){
            cost = dist[node.v][0] + it.c;
            if(cost != dist[it.v][0] && cost != dist[it.v][1]){ //分析 2-2
                if(cost < dist[it.v][1]){ //分析 2-3
                    dist[it.v][1] = cost;
                    //分析 2-4
                    if(cost < dist[it.v][0]) swap(dist[it.v][0], dist[it.v][1]); 
                    if(!visit[it.v]){ //分析 2-5
                        visit[it.v] = 1;
                        q.push_back({it.v, cost});
                    }

                }

            }

            cost = dist[node.v][1] + it.c; 
            if(cost != dist[it.v][0] && cost != dist[it.v][1]){ //分析 2-2
                if(cost < dist[it.v][1]){  //分析 2-3
                    dist[it.v][1] = cost;
                    //分析 2-4
                    if(cost < dist[it.v][0]) swap(dist[it.v][0], dist[it.v][1]);
                    if(!visit[it.v]){ //分析 2-5
                        visit[it.v] = 1;
                        q.push_back({it.v, cost});
                    }
                }
            }


        }
    }
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> n >> r){
        for(int i = 0; i < n; i++) edge[i].clear();
        for(int i = 0; i < r; i++){
            cin >> a >> b >> c;
            edge[a].push_back({b,c});
            edge[b].push_back({a,c});
        }

        cin >> q;
        cout << "Set #" << kase++ << "\n";
        while(q--){
            for(int i = 0; i < n; i++){
                dist[i][0] = INF;
                dist[i][1] = INF;
            }
            memset(visit, 0, sizeof(visit));

            cin >> start >> destination;
            dijkstra(start);
            if(dist[destination][1] == INF) cout << "?\n";
            else cout << dist[destination][1] << "\n";
        }
    }

    return 0;
}