641 字
2 分钟
Dijkstra
- Dijkstra
- 本算法用于求解图中两点的最短距离，要求无负权边 本质是贪心思想，将图中的点分成两类，一类为未确定最短距离的点， 另一类为已经确定的点，为了方便我将其称之为A点和B点。
- 首先将所有点初始化为B点，边长度为无穷大
- 读入边，起点和终点
- 将起点加入A点
- 在所有B点中，找到一个距起点距离最短的点，以这个点为中介来松弛其他边，接着把他加入A点
- 循环以上操作，直到无法进行下去
以下给出点权和优先的迪杰斯特拉算法代码模板，记录路径条数
#include <iostream>#include <algorithm>#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;int n, m, st, ed;int g[510][510]; // 邻接矩阵存储边权int weight[510]; // 每个点的点权（如救援队数量）int dist[510]; // 从起点到 i 的最短距离int num[510]; // 从起点到 i 的最短路径条数int w[510]; // 从起点到 i 的最大点权和bool vis[510]; // 标记是否已确定最短路
void dijkstra(int s) { // 1. 初始化 fill(dist, dist + 510, INF); dist[s] = 0; num[s] = 1; w[s] = weight[s];
for (int i = 0; i < n; i++) { // 2. 找到当前未访问过的最近的点 int u = -1, min_d = INF; for (int j = 0; j < n; j++) { if (!vis[j] && dist[j] < min_d) { u = j; min_d = dist[j]; } }
if (u == -1) return; // 剩余点不可达，直接退出 vis[u] = true;
// 3. 松弛操作 (Relaxation) for (int v = 0; v < n; v++) { if (!vis[v] && g[u][v] != INF) { if (dist[u] + g[u][v] < dist[v]) { // 发现更短的路 dist[v] = dist[u] + g[u][v]; num[v] = num[u]; // 路径数继承 w[v] = w[u] + weight[v]; // 点权和继承 } else if (dist[u] + g[u][v] == dist[v]) { // 发现等长的路 num[v] += num[u]; // 路径数累加 if (w[u] + weight[v] > w[v]) { w[v] = w[u] + weight[v]; // 更新最大点权 } } } } }}
int main() { cin >> n >> m >> st >> ed; for (int i = 0; i < n; i++) cin >> weight[i];
// 矩阵初始化为 INF fill(g[0], g[0] + 510 * 510, INF); while (m--) { int u, v, l; cin >> u >> v >> l; g[u][v] = g[v][u] = l; // 无向图 }
dijkstra(st);
cout << num[ed] << " " << w[ed] << endl; return 0;}注意：统计路径条数时num[i]+=num[j],也就是说必须继承自上一个点
实际操作的时候，我并未注意，导致犯错
- 错误代码示例鉴赏
for (int v = 0; v < n; v++) { if (g[u][v] != INF && !vis[v]) { if (dist[v] > dist[u] + g[u][v]) dist[v] = dist[u] + g[u][v], num[v] = num[u]; if (dist[v] == dist[u] + g[u][v])//这里会使得最后路径条数翻倍，想想为什么 num[v]+=num[u]; } }- 以下是PTA-GPLT真题113 AC code
#include <bits/stdc++.h>using namespace std;int n, m, s, d;int val[501], vmax[501], num[501];int g[501][501];int vis[501];int dist[501];int INF = 0x3f3f3f3f;int pre[501];int main(){ cin >> n >> m >> s >> d; for (int i = 0; i <= 500; i++) for (int j = 0; j < 500; j++) g[i][j] = INF; for (int i = 0; i <= 500; i++) dist[i] = INF; for (int i = 0; i < n; i++) cin >> val[i]; for (int i = 1; i <= m; i++) { int a, b, s; cin >> a >> b >> s; g[a][b] = g[b][a] = s; } int u = s; vis[u] = 1, dist[u] = 0, num[u] = 1, vmax[u] = val[u]; for (int i = 1; i <= n; i++) { int id, len = INF, p = 0; for (int v = 0; v < n; v++) { if (g[u][v] != INF && !vis[v]) { if (dist[v] > dist[u] + g[u][v]) { dist[v] = dist[u] + g[u][v], num[v] = num[u]; vmax[v] = vmax[u] + val[v]; pre[v] = u; } else if (dist[v] == dist[u] + g[u][v]) { num[v] += num[u]; if (vmax[v] < vmax[u] + val[v]) pre[v] = u, vmax[v] = vmax[u] + val[v]; } } } for (int v = 0; v < n; v++) { if (vis[v] == 0 && dist[v] < len) len = dist[v], id = v, p = 1; } if (p) u = id, vis[u] = 1; else break; } cout << num[d] << " " << vmax[d] << endl; vector<int> ans; for (int i = d;; i = pre[i]) { ans.push_back(i); if (i == s) break; } reverse(ans.begin(), ans.end()); for (int i=0;i<ans.size();i++){ cout << ans[i]; if(i!=ans.size()-1) cout << " "; } return 0;}tips: 可以用fill函数简化初始化过程
- 思维流程:
先不考虑限制，需要g[n][n]存储边长度，vis[n]对点分类，dist[n]存储最短距离
接着考虑限制，比如加入num数组统计条数，加入vmax统计点权最大，加入pre数组来保存路径
💡 Dijkstra 避坑四行诗 初始化要齐全：dist 设无穷，num[s] 拨到 1，起点权值先加上。
选点标记最优先：先在大海（未访问点）里捞针（最小 dist），捞出来立刻打上 vis 补丁。
松弛逻辑分两边：
更短路： 喜新厌旧，dist、num、vmax、pre 全部推翻重来（继承 u）。
等长路： 兼容并蓄，num 累加，vmax 和 pre 择优录取。
回溯路径逆着牵：从 d 开始找 pre[i]，最后 reverse 一下最稳妥。
🛠️ 针对你这次“小错误”的复盘 你刚才遇到的几个坑，其实是所有初学者必踩的“勋章”：
逻辑重叠 (if 变 else if)：这是对程序执行流的理解，踩过一次你这辈子都不会忘。
路径计数 (+= 还是 =)：这是对“状态转移”的理解，是动态规划的思想。
变量名覆盖 (s 既是起点又是边权)：这是工程习惯的磨炼。
- Gemini整理的代码模板：
#include <bits/stdc++.h>using namespace std;// 常量定义：510 留出一点余裕，0x3f 是竞赛常用的无穷大const int MAXN = 510;const int INF = 0x3f3f3f3f;int n, m, st, ed;int g[MAXN][MAXN]; // 邻接矩阵int val[MAXN]; // 每个点的点权int dist[MAXN]; // 最短距离int num[MAXN]; // 最短路径条数int vmax[MAXN]; // 最大点权和int pre[MAXN]; // 路径回溯：记录当前点的前驱bool vis[MAXN]; // 标记是否已访问void dijkstra(int start) { // 1. 使用 fill 或 memset 快速初始化 fill(dist, dist + MAXN, INF); fill(num, num + MAXN, 0); fill(vmax, vmax + MAXN, 0); fill(vis, vis + MAXN, false); dist[start] = 0; num[start] = 1; vmax[start] = val[start]; for (int i = 0; i < n; i++) { // 2. 找到未访问点中距离最近的 u int u = -1, min_d = INF; for (int j = 0; j < n; j++) { if (!vis[j] && dist[j] < min_d) { u = j; min_d = dist[j]; } } if (u == -1) break; // 剩余点不可达 vis[u] = true; // 标记 u 已确定 // 3. 松弛操作：用 u 更新邻居 v for (int v = 0; v < n; v++) { if (!vis[v] && g[u][v] != INF) { if (dist[u] + g[u][v] < dist[v]) { // 情况 A：发现更短的路，全部“继承”并“覆盖” dist[v] = dist[u] + g[u][v]; num[v] = num[u]; vmax[v] = vmax[u] + val[v]; pre[v] = u; } else if (dist[u] + g[u][v] == dist[v]) { // 情况 B：发现等长的路，路径数“累加” num[v] += num[u]; // 在等长前提下，择优录取（最大点权） if (vmax[u] + val[v] > vmax[v]) { vmax[v] = vmax[u] + val[v]; pre[v] = u; } } } } }}int main() { // 加速输入输出（可选） ios::sync_with_stdio(false); cin.tie(0); if (!(cin >> n >> m >> st >> ed)) return 0; // 初始化地图为 INF fill(g[0], g[0] + MAXN * MAXN, INF); for (int i = 0; i < n; i++) cin >> val[i]; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g[u][v] = g[v][u] = w; // 无向图 } dijkstra(st); // 输出第一行：路径数 和 最大点权 cout << num[ed] << " " << vmax[ed] << endl; // 输出第二行：回溯路径 vector<int> path; for (int i = ed; ; i = pre[i]) { path.push_back(i); if (i == st) break; } // 优雅的末尾无空格输出 for (int i = path.size() - 1; i >= 0; i--) { cout << path[i] << (i == 0 ? "" : " "); } return 0;} 分享
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时
相关文章 智能推荐