Poj 3255: Roadblocks

poj3255.md

Poj 3255: Roadblocks

題目

分析

求次短路徑……修改 Dijkstra，不只記錄到各點的最短距離（d[i]），還記錄次短距離（sd[i]）

實作上有幾點要注意（ 不確定這樣想對不對… ）：

1. 因次短路徑沒有最佳子結構（次短路徑的一部份不保證也是次短路徑），所以演算法不能提早跳出

2. priority_queue 裡存的就是那些被成功鬆弛過的點，因他們可能造成其它點也被鬆弛。 所以當某一點的 d[i] 或 sd[i] 被更新了，他也可能造成相鄰點的 d[i] sd[i] 被更新， 於是它就要被加到 priority_queue 裡。

AC Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

struct Edge {
    int to, cost;
};

typedef pair<int, int> P; // <d, v>
const int INF = 0x3f3f3f3f;

int N, R;
vector<Edge> g[5000];

int d[5000];
int sd[5000];

int solve() {
    fill(d, d + N, INF);
    fill(sd, sd + N, INF);
    priority_queue< P, vector<P>, greater<P> > pq;

    d[0] = 0;
    pq.push(P(0, 0));

    while (!pq.empty()) {
        P p = pq.top(); pq.pop();
        int v = p.second;

        if (sd[v] < p.first) // 比次短距離還大，沒用，跳過
            continue;

        for (size_t i = 0; i < g[v].size(); i++) {
            Edge& e = g[v][i];
            int nd = p.first + e.cost;
            if (nd < d[e.to]) { // 更新最短距離
                swap(d[e.to], nd);
                pq.push(P(d[e.to], e.to));
            }
            if (d[e.to] < nd && nd < sd[e.to]) { // 更新次短距離
                sd[e.to] = nd;
                pq.push(P(sd[e.to], e.to));
            }
        }
    }

    return sd[N-1];
}

int main() {
    scanf("%d %d", &N, &R);
    for (int i = 0; i < R; i++) {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        a--; b--;
        g[a].push_back(Edge{b, w});
        g[b].push_back(Edge{a, w});
    }

    printf("%d\n", solve());

    return 0;
}

that's hot!