您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

POJ 1135 Domino Effect：Dijkstra + 邊枚舉求最後倒下的骨牌

編輯：C++ 入門

問題描述

n 個關鍵骨牌，m 條邊（連接兩骨牌，長度為倒牌傳遞時間）。從 1 號骨牌推倒，求**最後倒下的時間**及**位置**（骨牌上或兩骨牌之間）。輸出格式固定。

核心邏輯

**Dijkstra 求最短路**：`dis[i]` = 1 號到 i 的最短時間 = i 倒下的時刻。最大值 `ans1 = max(dis[i])`，對應骨牌 `pos1`。
**枚舉每條邊 (u, v, w)**：若兩端倒下時間差 < w，則中間某處最後倒下。倒下時間 = `(dis[u] + dis[v] + w) / 2.0`。取最大值 `ans2`，記錄邊 `(u,v)`。
**比較**：若 `ans2 > ans1`，最後倒在邊上；否則最後倒在骨牌 `pos1` 上。

為什麼邊上時間是 (du + dv + w)/2？

設從 u 端傳遞需時 `du`，從 v 端需時 `dv`，邊長 w。兩波在中間相遇時：`du + x = dv + (w - x)` → `x = (dv + w - du)/2`。相遇時間 = `du + x = (du + dv + w)/2`。若 `|du - dv| >= w`，則一波先到達另一端，中間無相遇，最後倒下時間為 `max(du, dv)`（已在頂點考慮）。

完整代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 510;
const int INF = 0x3f3f3f3f;
int n, m;
int g[MAXN][MAXN];
int dis[MAXN];
bool vis[MAXN];

void dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1, mn = INF;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && dis[j] < mn) { mn = dis[j]; u = j; }
        if (u == -1) break;
        vis[u] = true;
        for (int v = 1; v <= n; v++)
            if (!vis[v] && g[u][v] < INF)
                dis[v] = min(dis[v], dis[u] + g[u][v]);
    }
}

int main() {
    int caseNo = 1;
    while (scanf("%d%d", &n, &m) == 2 && (n || m)) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                g[i][j] = (i == j) ? 0 : INF;

        for (int i = 0; i < m; i++) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            g[u][v] = g[v][u] = min(g[u][v], w);  // 可能有重邊取最小
        }

        printf("System #%d\n", caseNo++);
        if (n == 1) {
            printf("The last domino falls after 0.0 seconds, at key domino 1.\n\n");
            continue;
        }

        dijkstra();

        double ansNode = 0; int posNode = 1;
        for (int i = 1; i <= n; i++)
            if (dis[i] > ansNode) { ansNode = dis[i]; posNode = i; }

        double ansEdge = 0; int uEdge = -1, vEdge = -1;
        for (int u = 1; u <= n; u++)
            for (int v = u+1; v <= n; v++)
                if (g[u][v] < INF) {
                    double t = (dis[u] + dis[v] + g[u][v]) / 2.0;
                    if (t > ansEdge) { ansEdge = t; uEdge = u; vEdge = v; }
                }

        if (ansEdge > ansNode)
            printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n\n", ansEdge, uEdge, vEdge);
        else
            printf("The last domino falls after %.1f seconds, at key domino %d.\n\n", ansNode, posNode);
    }
    return 0;
}