POJ 3169 Layout：差分約束系統求最大距離

約束建模

• 喜歡：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 → x_i - x_{i+1} ≤ 0 → i+1 → i (0)

以 1 為源點跑最短路（Bellman-Ford/SPFA），dis[N] 即為 1 到 N 最大距離。

結果判斷

• 負環 → 輸出 -1（無解）
• dis[N] == INF → 輸出 -2（可無限遠）
• 否則輸出 dis[N]

SPFA 實現要點

bool spfa() {
    memset(dis, INF, sizeof(dis));
    dis[1] = 0; queue<int> q; q.push(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]) { inq[v] = 1; q.push(v); }
            }
        }
    }
    // 負環檢測：再松弛一輪
    for (int i = 0; i < cnt; i++)
        if (dis[e[i].v] > dis[e[i].u] + e[i].w) return false;
    return true;
}