UVa12950 - Even Obsession(Dijkstra's)

題目大意

Patricia 是個傑出的軟體工程師，但她有一些怪癖，喜歡偶數的事物，例如:喜歡買偶數張電影票、一天吃兩餐 or 四餐…等。
在 Patricia 所住的城市需要收過路費，Patricia 想從 1 到 x 點，她希望他可以被收偶數次的過路費，並且花費最少，你則必須輸出花費最小的數值為多少。

題目連結

重點觀念

• dijkstra’s by 大衛的筆記
• dijkstra’s 的變化題

分析

• 只有一點點小小的變化， dijkstra’s 是想要找出最短路徑，而這題目新增條件是要經過偶數個邊
• 那我們就分開操作，產生兩個 dist，一個裝在偶數邊時的最短距離、一個則裝奇數邊的最短距離。
  • 定義
    • odd_dist 奇數邊的最短距離
    • even_dist 偶數邊時的最短距離
    • root priority queue 當前的節點
    • cost priority queue 當前的成本
    • x root 可以抵達的任意節點
    • edge.c 當前的任意邊成本
    • {root, cost} 為 priority queue 型別，root 是節點、cost 是成本
  • 只要 edge.c[x] + odd_dist[root] > even_dist[x]， priority queue.push({x, edge.c[x] + odd_dist[root]})
  • 只要 edge.c[x] + even_dist[root] > odd_dist[x]， priority queue.push({x, edge.c[x] + even_dist[root]})

參考連結

UVa 12950 by bbsmax
UVa 12950 by Shadowdsp

題目程式碼

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

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 10020
#define INF 2100000000
using namespace std;
struct Edge{
    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;
    }
};

int c, v;
int a, b, cost;
vector<Edge> edge[MAXN];
int odd_dist[MAXN], even_dist[MAXN]; 

void dijkstra(int root){
    deque<Edge> q;
    q.push_back({root,0});
    even_dist[root] = 0;
    //odd_dist[root] = 0;

    int cost;
    while(!q.empty()){
        Edge node = q.front(); q.pop_front();
        //cout << node.v << " " << node.c << "\n";
        for(auto it: edge[node.v]){ 
            cost = odd_dist[node.v] + it.c;
            //cout << "even dist " << cost << " " << even_dist[it.v] << "\n";
            if(cost < even_dist[it.v]){ //分析 2
                q.push_back({it.v, cost});
                even_dist[it.v] = cost;
            }

            cost = even_dist[node.v] + it.c;
            if(cost < odd_dist[it.v]){
                q.push_back({it.v, cost});
                odd_dist[it.v] = cost;
            }
        }
    }
}


int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> c >> v){
        for(int i = 1; i <= c; i++){
            edge[i].clear();
            even_dist[i] = INF;
            odd_dist[i] = INF;
        }
        for(int i = 0; i < v; i++){
            cin >> a >> b >> cost;
            edge[a].push_back({b,cost}); //題目為雙向邊
            edge[b].push_back({a,cost});
        }
        dijkstra(1);
        if(even_dist[c] == INF) cout << "-1\n";
        else cout << even_dist[c] << "\n";
    }
    return 0;
}