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;
}
