HDU 3790 最短路徑問題 — 雙準則 Dijkstra（距離優先、花費次之）

問題描述

圖中邊有兩個權值：距離 d 與花費 p。求從 s 到 t 的路徑，優先距離最短，距離相等時花費最小。n ≤ 1000，存在重邊。

改進 Dijkstra

狀態：dis1[u] 為到 u 的最短距離，dis2[u] 為對應最小花費。

松弛條件：

if (new_dist < dis1[v] || (new_dist == dis1[v] && new_cost < dis2[v])) {
    dis1[v] = new_dist;
    dis2[v] = new_cost;
}

重邊處理

讀入邊時保留距離最小、距離相等則花費最小的邊：

if (d < Map[a][b] || (d == Map[a][b] && p < cost[a][b])) {
    Map[a][b] = Map[b][a] = d;
    cost[a][b] = cost[b][a] = p;
}

參考代碼 (C++)

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

const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
int Map[MAXN][MAXN], cost[MAXN][MAXN];
int dis1[MAXN], dis2[MAXN];
int n, m;

void init() {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            if (i == j) Map[i][j] = cost[i][j] = 0;
            else Map[i][j] = cost[i][j] = INF;
        }
}

void dijkstra(int s) {
    bool vis[MAXN] = {0};
    for (int i = 1; i <= n; ++i) {
        dis1[i] = Map[s][i];
        dis2[i] = cost[s][i];
    }
    vis[s] = 1;
    for (int i = 1; i <= n; ++i) {
        int u = -1, minD = INF, minC = INF;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && (dis1[j] < minD || (dis1[j] == minD && dis2[j] < minC))) {
                minD = dis1[j]; minC = dis2[j]; u = j;
            }
        if (u == -1) break;
        vis[u] = 1;
        for (int v = 1; v <= n; ++v) if (!vis[v]) {
            int nd = dis1[u] + Map[u][v];
            int nc = dis2[u] + cost[u][v];
            if (nd < dis1[v] || (nd == dis1[v] && nc < dis2[v])) {
                dis1[v] = nd; dis2[v] = nc;
            }
        }
    }
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        if (!n || !m) break;
        init();
        while (m--) {
            int a,b,d,p; scanf("%d%d%d%d", &a,&b,&d,&p);
            if (d < Map[a][b] || (d == Map[a][b] && p < cost[a][b])) {
                Map[a][b] = Map[b][a] = d;
                cost[a][b] = cost[b][a] = p;
            }
        }
        int s, t; scanf("%d%d", &s, &t);
        dijkstra(s);
        printf("%d %d\n", dis1[t], dis2[t]);
    }
    return 0;
}

複雜度

• 時間：O(n²)（鄰接矩陣 + 簡單 Dijkstra），n=1000 可接受。
• 空間：O(n²) 存圖。

總結

本題是雙權值最短路的模板題。關鍵在於松弛條件的字典序比較（先距離後花費），以及重邊的預處理。若 n 更大可改用鄰接表 + 優先隊列優化至 O(m log n)。