您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 4725 The Shortest Path in Nya Graph：Dijkstra + 虛擬層節點建圖

編輯：C++ 入門

題目大意

給定 n 個節點、m 條無向邊，每個節點屬於某一層。相鄰層間移動代價為 c。求從節點 1 到節點 n 的最小代價。

核心思路：虛擬層節點建圖 + Dijkstra

關鍵在於如何高效處理「層間移動代價 c」。若直接連接所有層間節點，邊數會爆炸。解法是引入虛擬層節點（匯點）：

建圖策略

每層設置一個虛擬節點（編號 `layer_id + N`）
節點 → 所屬層虛擬節點：代價 0（單向）
虛擬節點 → 節點：代價 0（單向）
節點 → 相鄰層虛擬節點：代價 c（單向）
相鄰層虛擬節點互連：若兩層均有節點，雙向連接，代價 c
原圖邊保持雙向，代價為給定值

此建圖方式將層間轉移簡化為經過虛擬節點，邊數從 O(N²) 降為 O(N + M)。

關鍵細節：為何「節點 → 當前層虛擬節點」會 WA？

作者嘗試過 `addEdge(i, d+N, 0)` 但 WA。正確做法是虛擬節點 → 節點（代價 0），即 `addEdge(d+N, i, 0)`。原因在於：

從節點出發需先「進入」虛擬層（代價 c 到相鄰層虛擬節點），再「走出」到目標節點（代價 0）
若反向連接，會破壞「層間移動必須付費 c」的語義

完整代碼實現

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

typedef pair<int,int> pii;
const int N = 100000;
const int INF = 0x3f3f3f3f;

int n, m, c;
int dist[N*3+10], vis[N*3+10];
int nindex, head[N*3+10];

struct Edge { int to, val, next; } edge[N*20];

inline void addEdge(int u, int v, int val) {
    edge[nindex] = {v, val, head[u]};
    head[u] = nindex++;
}

void init() {
    nindex = 0;
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));
    scanf("%d%d%d", &n, &m, &c);
    
    for (int i = 1; i <= n; i++) {
        int layer; scanf("%d", &layer);
        vis[layer] = 1;
        // 虛擬節點 → 實體節點（代價0）
        addEdge(layer + N, i, 0);
        // 實體節點 → 相鄰層虛擬節點（代價c）
        if (layer > 1) addEdge(i, layer + N - 1, c);
        if (layer < n) addEdge(i, layer + N + 1, c);
    }
    
    for (int i = 0; i < m; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    
    // 相鄰層虛擬節點互連
    for (int i = 2; i <= n; i++) {
        if (vis[i] && vis[i-1]) {
            addEdge(i+N, i-1+N, c);
            addEdge(i-1+N, i+N, c);
        }
    }
}

int dijkstra() {
    memset(dist, INF, sizeof(dist));
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[1] = 0;
    pq.push({0, 1});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (int e = head[u]; e != -1; e = edge[e].next) {
            int v = edge[e].to, w = edge[e].val;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist[n] == INF ? -1 : dist[n];
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        init();
        printf("Case #%d: %d\n", cas, dijkstra());
    }
    return 0;
}