POJ 3169 Layout 差分約束系統 SPFA 解法

約束轉換

• 最大距離 A B D：x_B - x_A ≤ D → 邊 A→B (D)
• 最小距離 A B D：x_A - x_B ≤ -D → 邊 B→A (-D)
• 順序約束隱含：x_{i+1} - x_i ≥ 0 → i+1→i (0)

SPFA 求最短路

void spfa() {
    fill(dis, dis+n+1, INF); dis[1] = 0;
    queue q; q.push(1); inq[1] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for (int i=head[u]; ~i; i=e[i].next) {
            int v = e[i].v;
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if (!inq[v]) {
                    if (++cnt[v] > n) { has_cycle = true; return; }
                    inq[v] = 1; q.push(v);
                }
            }
        }
    }
}

結果判斷

• has_cycle → -1（矛盾）
• dis[n] == INF → -2（無上界）
• 否則 → dis[n]