HDOJ 3790 最短路徑問題：Dijkstra 雙權值（距離+花費）

問題描述

無向圖，n ≤ 1000，m 條邊。每條邊有長度 d 和花費 p。求從 s 到 t 的最短距離；若最短距離有多條路徑，取花費最小者。

Dijkstra 修改比較邏輯

標準 Dijkstra 中，松弛條件改為：

if (dist[v] > dist[u] + d) {
    dist[v] = dist[u] + d;
    cost[v] = cost[u] + p;
} else if (dist[v] == dist[u] + d && cost[v] > cost[u] + p) {
    cost[v] = cost[u] + p;
}

優先隊列按 (dist, cost) 排序，或僅按 dist，相等時在鬆弛中處理花費。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, MAXN = 1005;
struct Edge { int to, d, p, nxt; } e[MAXN*MAXN];
int head[MAXN], ecnt, n, m;
int dist[MAXN], cost[MAXN]; bool vis[MAXN];
void addEdge(int u, int v, int d, int p) {
    e[ecnt] = {v, d, p, head[u]}; head[u] = ecnt++;
}
void dijkstra(int s, int t) {
    fill(dist, dist+n+1, INF); fill(cost, cost+n+1, INF); fill(vis, vis+n+1, false);
    dist[s] = cost[s] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.emplace(0, s);
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (vis[u]) continue; vis[u] = true;
        if (u == t) break;
        for (int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].to, nd = du + e[i].d, nc = cost[u] + e[i].p;
            if (dist[v] > nd) {
                dist[v] = nd; cost[v] = nc;
                pq.emplace(nd, v);
            } else if (dist[v] == nd && cost[v] > nc) {
                cost[v] = nc;
                pq.emplace(nd, v); // 重新入隊以傳播更小花費
            }
        }
    }
    cout << dist[t] << ' ' << cost[t] << '\n';
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    while (cin >> n >> m, n || m) {
        fill(head, head+n+1, -1); ecnt = 0;
        for (int i = 0; i < m; ++i) {
            int a, b, d, p; cin >> a >> b >> d >> p;
            addEdge(a, b, d, p); addEdge(b, a, d, p);
        }
        int s, t; cin >> s >> t;
        dijkstra(s, t);
    }
    return 0;
}

注意事項

• 圖可能有重邊，建圖時保留最小 d，同 d 下保留最小 p。
• 優先隊列可能重複入隊同一節點，需 vis 數組標記最終確定。