Dijkstra 算法
- 算法前提：在沒有負邊的情況下使用。
- 算法思路：將結點分成已確定最短路長度的點集 S 和未確定最短路長度的點集 T，每次從 T 集合中選取最短路長度最小的結點移到 S 集合中，并對其出邊執行更新操作
- 從T集合中，選取一個最短路長度最小的結點，移到S集合中。
- 對那些剛剛被加入S集合的結點的所有出邊執行松弛操作。
?
struct edge { int v, w; // 邊的終點和權值
};
struct node { int dis, u; // 距離和頂點bool operator > (const node &a ) const {return dis>a.dis; // 優先隊列比較函數，小根堆}
};
vector<edge> e[MAXN]; // 鄰接表存儲邊
int dis[MAXN], vis[MAXN]; // dis存儲最短距離，vis標記是否已確定最短距離
priority_queue<node, vector<node>, greater<node>> q; // 小根堆優先隊列void dijkstra(int n, int s) {memset(dis, 0x3f, (n + 1) * sizeof(int)); // 初始化最短距離為無窮大memset(vis, 0, (n + 1) * sizeof(int)); // 初始化標記數組為0dis[s] = 0; // 起點到自身的距離為0q.push({0, s}); // 起點入隊while (!q.empty()) {int u = q.top().u; // 取出距離最小的頂點q.pop(); if (vis[u]) continue; // 如果已確定最短距離，跳過vis[u] = 1; // 標記為已確定最短距離for (auto ed : e[u]) { // 遍歷u的所有出邊int v = ed.v, w = ed.w; // 邊的終點和權值// 如果可以通過u得到更短的距離到vif (dis[v] > dis[u] + w) {dis[v] = dis[u] + w; // 更新最短距離q.push({dis[v], v}); // 將v入隊}}}
}?
?
?例題
#i#include <bits/stdc++.h>
using namespace std;const int MAXN = 2010; // 最大節點數（人數），題目中 n≤2000，這里多開一點防止越界
double dis[MAXN]; // 存儲從起點 A 到各節點能保留的金額比例，初始化為極小值
bool vis[MAXN]; // 標記節點是否已確定最長路徑，避免重復處理
int n, m, A, B; // n 是總人數，m 是轉賬對數，A 是轉賬起點，B 是轉賬終點// 邊的結構體，用于構建圖的鄰接表，to 表示轉賬目標節點，rate 表示轉賬后能保留的比例（1 - 手續費比例）
struct Edge {int to;double rate;
};vector<Edge> graph[MAXN]; // 鄰接表存儲圖結構，graph[u] 存所有從 u 出發能轉賬到的節點及對應保留比例// 優先隊列中的節點結構體，用于 Dijkstra 算法，node 表示節點編號，val 表示到達該節點時能保留的金額比例
struct Node {int node;double val;// 重載小于運算符，讓優先隊列按照 val 從大到小排序（大頂堆），這樣每次取出當前能保留比例最大的路徑bool operator<(const Node& other) const {return val < other.val;}
};// Dijkstra 算法實現，求解從 A 出發到各節點能保留的最大金額比例
void dijkstra() {// 初始化 dis 數組，將起點 A 的保留比例設為 1（還沒轉賬，金額完整保留），其他設為極小值fill(dis, dis + MAXN, 0);dis[A] = 1;// 優先隊列，大頂堆，用于每次選當前能保留比例最大的路徑拓展priority_queue<Node> pq;pq.push({A, 1});while (!pq.empty()) {Node cur = pq.top();pq.pop();int u = cur.node;double currentRate = cur.val;// 如果當前節點已經處理過（已確定最長路徑），跳過if (vis[u]) continue;vis[u] = true; // 標記為已處理// 遍歷當前節點 u 的所有鄰接邊，嘗試更新鄰接節點的最大保留比例for (const Edge& e : graph[u]) {int v = e.to;double newRate = currentRate * e.rate;// 如果經過 u 轉賬到 v 能獲得更大的保留比例，就更新，并將 v 加入隊列等待處理if (newRate > dis[v]) {dis[v] = newRate;pq.push({v, newRate});}}}
}int main() {// 輸入總人數 n 和轉賬對數 mscanf("%d%d", &n, &m);for (int i = 0; i < m; ++i) {int x, y, z;// 輸入轉賬的兩人 x、y 以及手續費比例 zscanf("%d%d%d", &x, &y, &z);double rate = 1 - z / 100.0; // 計算轉賬后能保留的比例（1 - 手續費比例）// 因為是互相轉賬，所以添加兩條有向邊（x 到 y 和 y 到 x）graph[x].push_back({y, rate});graph[y].push_back({x, rate});}// 輸入轉賬起點 A 和終點 Bscanf("%d%d", &A, &B);dijkstra(); // 執行 Dijkstra 算法，計算從 A 到各節點的最大保留比例// B 要收到 100 元，那么 A 需要的初始金額 = 100 / （A 到 B 能保留的比例）double result = 100 / dis[B];// 輸出結果，精確到小數點后 8 位printf("%.8lf\n", result);return 0;
}
