还未更新完毕。
本文中 $n$ 表示点的数量, $m$ 表示边的数量。
1. Dijkstra 时间复杂度 $O(n^2)$
AcWing 849. Dijkstra求最短路 I
AcWing 1132. 农场派对
适用情况:点少,边多。
负权边: 不可用
核心思路 - 贪心
起点为一个集合,每次选择距离集合最近的点,加入集合,并更新距离。
核心代码
for (int i = 0; i < n; ++ i )
{
int t = -1;
for (int j = 1; j <= n; ++ j )
if (!st[j] && (t == -1 || dist[t] > dist[j])) // <---
t = j;
st[t] = true;
for (int j = 1; j <= n; ++ j )
dist[j] = min(dist[j], dist[t] + g[t][j]); // <---
}
变形题
须在 <---
处依照题意做更改
AcWing 4240. 青蛙
AcWing 4241. 货物运输
2. Dijkstra堆优化 时间复杂度 $O((n+m)logn)$
AcWing 850. Dijkstra求最短路 II
适用情况:多点,多边。
负权边: 不可用
核心思路 - 贪心
用优先队列选出权重最小的边,更新邻点。
核心代码
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y, distance = t.x;
if (st[ver])
continue;
st[ver] = true;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
变形题
3. spfa 时间复杂度 最坏 $(nm)$ 一般远小于 $O(nm)$
AcWing 851. spfa求最短路
由 bellman-ford
算法演变而成。
适用情况:几乎所有情况,除特意卡该算法。
负权边:可用
核心思路
bellman-ford + BFS
核心代码
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i] )
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
变形题
AcWing 4871. 最早时刻
AcWing 852. spfa判断负环
AcWing 4242. 货币兑换
AcWing 904. 虫洞
4. Floyd 时间复杂度 $O(n^3)$
核心思路 - DP
核心代码
for (int k = 1; k <= n; ++ k )
for (int i = 1; i <= n; ++ i )
for (int j = 1; j <= n; ++ j )
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
变形题
AcWing 4243. 传递信息
AcWing 4872. 最短路之和
5. BFS 时间复杂度 $O(nm)$ $n、m$ 为矩形的长和宽
核心思路
核心代码
while (q.size())
{
auto t = q.front();
q.pop();
for (int i = 0; i < 4; ++ i )
{
int tx = t.x + dx[i], ty = t.y + dy[i];
if (tx < 0 || ty < 0 || tx >= n || ty >= m || g[tx][ty] == '1')
continue;
g[tx][ty] = '1';
dist[tx][ty] = dist[t.x][t.y] + 1;
if (tx == n - 1 && ty == m - 1)
return dist[tx][ty];
q.push({tx, ty});
}
}
变形题
掌握要求
- 蓝桥杯:
floyd
>spfa
>dijkstra堆优化
>dijkstra
- CSP:
floyd
>dijkstra堆优化
>dijkstra
>bellman-ford
>spfa
# orz
大佬!
佬,你很谦虚,你才是佬
我是蒟蒻
催更ing~
(づ ̄ 3 ̄)づ