HDU 2544 完整解析：Bellman-Ford 求最短路

N 個路口（N ≤ 100），M 條雙向路（M ≤ 10000）。1 號商店到 N 號賽場最短時間。邊權為正。

Bellman-Ford 核心思想

將無向邊拆為兩條有向邊。
dis[1] = 0，其餘 INF。
重複 N-1 輪松弛所有邊：
if (dis[v] > dis[u] + w) dis[v] = dis[u] + w。
若某輪無更新則提前結束。

完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 110;
const int MAXE = 20020;
const int INF = 1e9;

struct Edge { int from, to, cost; } edges[MAXE];
int dis[MAXV];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int V, E;
    while (cin >> V >> E, V || E) {
        int ecnt = 0;
        for (int i = 0; i < E; i++) {
            int a, b, c; cin >> a >> b >> c;
            edges[ecnt++] = {a, b, c};
            edges[ecnt++] = {b, a, c}; // 無向拆雙向
        }
        
        fill(dis, dis + V + 1, INF);
        dis[1] = 0;
        
        while (true) {
            bool updated = false;
            for (int i = 0; i < ecnt; i++) {
                int u = edges[i].from, v = edges[i].to, w = edges[i].cost;
                if (dis[u] != INF && dis[u] + w < dis[v]) {
                    dis[v] = dis[u] + w;
                    updated = true;
                }
            }
            if (!updated) break;
        }
        
        cout << dis[V] << '\n';
    }
    return 0;
}

關鍵點總結

• 無向圖轉有向：每條邊存兩次，相反方向
• Bellman-Ford 適用性：V=100, E=20000，O(VE)=2×10⁶ 極快
• 提前終止優化：無更新即收斂
• 邊權為正：無負環風險，Dijkstra 更快但 BF 更簡單
• 多測資：0 0 結束