POJ 3114 Countries in War（強連通分量縮點 + Dijkstra 最短路）

POJ 3114 Countries in War - 強連通分量縮點 + 最短路

有向圖邊有長度，查詢兩點間最短路。先縮點（強連通分量內距離 0），再跑 Dijkstra。

算法流程

1. Tarjan 算法求強連通分量 (SCC)，得到縮點後的 DAG
2. 縮點建圖：SCC 內距離 0，SCC 間保留最小邊權
3. 多源 Dijkstra：對每個查詢起點所在 SCC 跑一次 Dijkstra，緩存結果

關鍵代碼片段

// Tarjan 求 SCC
int dfn[N], low[N], stk[N], top, timer, sccCnt, bel[N];
bool inStk[N];
vector scc[N];

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++timer;
    stk[top++] = u; inStk[u] = true;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (dfn[u] < low[v]) e[i].isBridge = true;
        } else if (inStk[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        sccCnt++;
        do { int x = stk[--top]; inStk[x]=0; bel[x]=sccCnt; scc[sccCnt].push_back(x); }
        while (x != u);
    }
}

// 縮點建圖
vector G[N];
int deg[N];
void buildDAG() {
    for (int i = 0; i < m; i++) {
        int u = bel[e[i].from], v = bel[e[i].to];
        if (u != v) G[u].push_back(v), deg[v]++;
    }
}

// Dijkstra 求最短路
int dist[N][N], cost[N][N];
void dijkstra(int n, int s) {
    bool vis[N]; fill(dist[s], dist[s]+n+1, INF);
    dist[s][s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1, mn = INF;
        for (int j = 1; j <= n; j++) if (!vis[j] && dist[s][j] < mn) mn = dist[s][u=j];
        if (u == -1) break;
        vis[u] = true;
        for (int v = 1; v <= n; v++) if (!vis[v] && dist[s][u] + cost[u][v] < dist[s][v])
            dist[s][v] = dist[s][u] + cost[u][v];
    }
}

完整查詢處理

int q; scanf("%d", &q);
bool used[N] = {0};
while (q--) {
    int a, b; scanf("%d%d", &a, &b);
    int u = bel[a], v = bel[b];
    if (!used[u]) { dijkstra(sccCnt, u); used[u] = true; }
    if (u == v) printf("0\n");
    else if (dist[u][v] == INF) printf("Nao e possivel entregar a carta\n");
    else printf("%d\n", dist[u][v]);
}

優化要點

• Floyd O(V³) 會超時 (V≤500)，改用 Dijkstra O(V²) 或堆優化
• 查詢起點重複時緩存 Dijkstra 結果
• 邊權較小，鄰接矩陣存儲 cost 方便

複雜度分析

• Tarjan：O(N + M)
• Dijkstra (鄰接矩陣)：O(V²) 每次，V = SCC 數 ≤ N
• 總時間：可接受