#创作计划# 图论笔记
2026-09-25 14:03:02
发布于：上海
22阅读
0回复
0点赞
点个赞评个论喵。
常见最短路
是一种单源最短路算法。
解决无权图的最短路问题。
采用 解决，可以证明最先到达的一定是最短路。
该算法维护一个距离数组 ， 表示为 至 的最短距离。
是一种单源最短路算法。
解决非负权边的最短路问题。
采用贪心策略，每次访问离 最近且未被访问的顶点，直至扩展完所有点。
该算法维护一个距离数组 ， 表示为 至 的最短距离。
是一种单源最短路算法。
解决任意权边的最短路问题。
进行 次循环，每次前进一步，判断经过的边是否因此而有更优松弛。
该算法维护一个距离数组 ， 表示为 至 的最短距离。
是一种单源最短路算法。
解决任意权边的最短路问题。
是 的优化。
采用队列进行，对于所有上轮仍在更新的点进行松弛。
该算法维护一个距离数组 ， 表示为 至 的最短距离。
是一种全源最短路算法。
解决任意权边的最短路问题。
对于可能出现松弛的情况进行完整的枚举。
该算法维护一个距离数组 ， 表示从 到 的最短距离。
判断负环：
1. 对于一个点跑了不少于 次。
2. 中有 。
例题 P4011
注意到每次移动所耗费时间相同，采用 解决。
注意到 非常小，考虑状压所拥有钥匙情况。
注意实现细节即可。即：起点可能会有钥匙 一个位置可能有多个钥匙等
#include <bits/stdc++.h>
using namespace std;
#define y1 qwer
int n, m, p, k, s;
int door[15][15][15][15];
int keys[15][15];
int dis[15][15][1 << 15];
int dir[4][2] {1, 0, -1, 0, 0, 1, 0, -1};
int bfs() {
memset(dis, -1, sizeof dis);
queue <pair <pair <int, int>, int> > q;
int st = keys[1][1];
dis[1][1][st] = 0;
q.push({{1, 1}, st});
while (!q.empty()) {
auto cur = q.front();
int x = cur.first.first, y = cur.first.second, state = cur.second;
q.pop();
if (x == n && y == m) return dis[x][y][state];
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0], ny = y + dir[i][1];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
if (door[x][y][nx][ny] != 0) {
if (door[x][y][nx][ny] > 0)
if (!(state >> (door[x][y][nx][ny] - 1) & 1)) continue;
int nst = state | keys[nx][ny];
if (dis[nx][ny][nst] == -1) {
dis[nx][ny][nst] = dis[x][y][state] + 1;
q.push({{nx, ny}, nst});
}
}
}
}
} return -1;
}
int main() {
cin >> n >> m >> p >> k;
memset(door, -1, sizeof door);
for (int i = 1; i <= k; i++) {
int x1, y1, x2, y2, g;
cin >> x1 >> y1 >> x2 >> y2 >> g;
door[x1][y1][x2][y2] = g;
door[x2][y2][x1][y1] = g;
} cin >> s;
for (int i = 1; i <= s; i++) {
int x, y, q;
cin >> x >> y >> q;
keys[x][y] |= (1 << (q - 1));
} cout << bfs();
return 0;
}
例题 P8817
注意到 的时间复杂度可以通过。
我们枚举 ，预处理 。
显然预处理每个点所有可以 步通达的点中权值前 大的点所需的时间是 。
为防止重复，选择最大、次大和次次大的点，可以证明的是，这样一定能保证不重复。
时间复杂度约为 ，可以通过。
代码没写。
有帮助，赞一个