POJ 3463：Sightseeing——次短路 Dijkstra 變體

題目描述

有向圖，求從 S 到 T 的最短路和嚴格次短路條數。N ≤ 1000, M ≤ 10000。

狀態擴展 Dijkstra

每個節點維護兩個距離：dist[v][0] 最短，dist[v][1] 次短（嚴格大於最短）。對應計數 cnt[v][0/1]。

優先隊列元素

(距離, 頂點, 類型)  // 類型 0=最短, 1=次短

松弛邏輯

從狀態 (u, t) 拉出，對邊 u→v 權 w，新距 d = dist[u][t] + w：

• d < dist[v][0]：次短←最短，最短←d，計數轉移
• d == dist[v][0]：最短計數累加
• dist[v][0] < d < dist[v][1]：次短←d，計數繼承
• d == dist[v][1]：次短計數累加

C++ 實現（核心）

struct State { int v, d, t; bool operator<(State o) const { return d > o.d; } };
priority_queue<State> pq;
pq.push({S,0,0}); dist[S][0]=0; cnt[S][0]=1;
while(!pq.empty()) {
    State cur=pq.top(); pq.pop();
    if(cur.d > dist[cur.v][cur.t]) continue;
    for(Edge e: adj[cur.v]) {
        int nd=cur.d+e.w, v=e.v;
        if(nd < dist[v][0]) {
            dist[v][1]=dist[v][0]; cnt[v][1]=cnt[v][0];
            dist[v][0]=nd; cnt[v][0]=cnt[cur.v][cur.t];
            pq.push({v,nd,0}); pq.push({v,dist[v][1],1});
        } else if(nd == dist[v][0]) {
            cnt[v][0] += cnt[cur.v][cur.t];
        } else if(nd < dist[v][1]) {
            dist[v][1]=nd; cnt[v][1]=cnt[cur.v][cur.t];
            pq.push({v,nd,1});
        } else if(nd == dist[v][1]) {
            cnt[v][1] += cnt[cur.v][cur.t];
        }
    }
}
printf("%d %d\n", dist[T][1], cnt[T][1]);

複雜度

• 時間：O(M log N) 狀態數翻倍但同階
• 空間：O(N+M)