HDU 3790 完整解析：最短路徑下的最小花費

N 個點（N ≤ 1000），M 條無向邊（M ≤ 100,000）。每邊有長度 d 和花費 p。求從 S 到 T 的最短距離，若有多條最短路徑，取花費最小者。

核心邏輯：距離優先，花費次優

標準最短路演算法（Dijkstra 或 SPFA），松弛條件雙重判斷：

if (dis[v] > dis[u] + w) {
    dis[v] = dis[u] + w;
    cost[v] = cost[u] + p;
    push(v);
} else if (dis[v] == dis[u] + w) {
    if (cost[v] > cost[u] + p) {
        cost[v] = cost[u] + p;
        // 注意：距離未改變，通常不需重新入隊（SPFA 可選）
    }
}

重邊處理：輸入時保留最優

同一點對可能有多條邊，輸入時保留：

• 長度最小者
• 長度相等時，花費最小者

完整 AC 程式碼

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

const int MAXN = 1210;
const int INF = 1e9;

int n, m;
int dist[MAXN][MAXN], cost[MAXN][MAXN];
int d[MAXN], c[MAXN];
bool inq[MAXN];

void init() {
    for (int i = 1; i <= n; i++) {
        fill(dist[i], dist[i] + n + 1, INF);
        fill(cost[i], cost[i] + n + 1, INF);
    }
    fill(d, d + n + 1, INF);
    fill(c, c + n + 1, INF);
}

void spfa(int s) {
    queue q;
    d[s] = 0; c[s] = 0;
    q.push(s); inq[s] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        
        for (int v = 1; v <= n; v++) {
            if (dist[u][v] == INF) continue;
            
            if (d[v] > d[u] + dist[u][v]) {
                d[v] = d[u] + dist[u][v];
                c[v] = c[u] + cost[u][v];
                if (!inq[v]) { q.push(v); inq[v] = true; }
            } else if (d[v] == d[u] + dist[u][v]) {
                if (c[v] > c[u] + cost[u][v]) {
                    c[v] = c[u] + cost[u][v];
                    // 距離未變，不必入隊（可選優化）
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    while (cin >> n >> m, n || m) {
        init();
        for (int i = 0; i < m; i++) {
            int a, b, d, p;
            cin >> a >> b >> d >> p;
            if (d < dist[a][b]) {
                dist[a][b] = dist[b][a] = d;
                cost[a][b] = cost[b][a] = p;
            } else if (d == dist[a][b] && p < cost[a][b]) {
                cost[a][b] = cost[b][a] = p;
            }
        }
        int S, T;
        cin >> S >> T;
        spfa(S);
        cout << d[T] << ' ' << c[T] << '\n';
    }
    return 0;
}

關鍵點總結

• 雙準則松弛：距離為主鍵，花費為次鍵
• 重邊預處理：輸入階段保留最優邊，減少圖規模
• SPFA 適用：N=1000, M=1e5，SPFA 平均快，注意負環（本題無負權）
• 多測資：以 0 0 結束