分层图最短路 算法详解与模板


转载注明出自bestsort.cn,谢谢合作


分层图最短路

应用场景

分层图最短路在最短路的基础上,增加了一个条件:可将 n 条边的权值变为 0. 比如说下图: 那么最短路肯定是如下图 但是如果我们能把一条边的权值变为 0 的话,最短路应该是下面这个样子 而分层图就是用来解决这类问题的. 仔细回想下最短路的 floyd 算法,每次对于一个点 k ,用$dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j])$来择优选择.这里的分层图也是一样的道理,每次对 此条边免费此条边不免费 进行 DP,最终结果便是最优解. 设会有 K 次免费机会,则 dis的状态转移方程为: $dis[i][j]=min(dis[father][j-1],dis[father][j]+w)$ 其中, $father$ 表示节点$i$的父亲节点,$w$ 表示节点 $i$ 到 $j$ 的边权.当 $j-1>=k$ 时,$dis[father][j]=INF$ ($INF$为无穷大,通常用0x3f3f3f3f表示) 事实上,这个 DP 就相当于把每个结点拆分成了 $k+1$ 个结点,每个新结点代表使用不同多次免费通行后到达的原图结点。换句话说,就是每个结点 $u[i]$ 表示使用 i 次免费通行权限后到达 $u$ 结点。 在代码实现里面,核心代码只不过在最短路的基础上修改了几行用于 DP,代码本身并不难.


这里代码中的最短路部分采用的算法是 **Dijkstra+堆优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <list>
#include <cstring>
#include <map>
#include <limits>
#include <cmath>
#define IN freopen("in.txt","r",stdin);
using namespace std;
typedef long long int ll;
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;

struct State
{ // 优先队列的结点结构体
int v, w, cnt; // cnt 表示已经使用多少次免费通行权限
State() {}
State(int v, int w, int cnt) : v(v), w(w), cnt(cnt) {}
bool operator<(const State &rhs) const { return w > rhs.w; }
};
struct node
{
int v;
int w;
int next;
/* data */
}edge[maxn];
priority_queue<State>pq;
int n,t,m,k,u,v,w,s;
int cnt;
bool vis[maxn][20];
int dis[maxn][20];
int head[maxn];

void add(int u,int v,int w){ //链式前向星存边
edge[cnt] = {v,w,head[u]};
head[u] = cnt++;
}

void dijkstra()
{
memset(dis, 0x3f, sizeof(dis));
dis[s][0] = 0;
pq.push(State(s, 0, 0)); // 到起点不需要使用免费通行权,距离为零
while (!pq.empty())
{
State top = pq.top();
pq.pop();
int u = top.v;
int nowCnt = top.cnt;
if (vis[u][nowCnt])
continue;
vis[u][nowCnt] = true;

for (int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].v, w = edge[i].w;
if (nowCnt < k && dis[v][nowCnt + 1] > dis[u][nowCnt])
{ // 可以免费通行
dis[v][nowCnt + 1] = dis[u][nowCnt];
pq.push(State(v, dis[v][nowCnt + 1], nowCnt + 1));
}
if (dis[v][nowCnt] > dis[u][nowCnt] + w)
{ // 不可以免费通行
dis[v][nowCnt] = dis[u][nowCnt] + w;
pq.push(State(v, dis[v][nowCnt], nowCnt));
}
}
}
}

int main()
{
//IN;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(head,-1,sizeof (head));
cin >> n >> m >> k;
cin >> s >> t;
while (m--)
{
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
int ans = INF;
dijkstra();
for (int i = 0; i <= k; ++i)
ans = min(ans, dis[t][i]); // 对到达终点的所有情况取最优值
cout << ans << endl;
}

觉得文章不错的话可以请我喝一杯茶哟~
  • 本文作者: bestsort
  • 本文链接: https://bestsort.cn/2019/05/07/703/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-SA 许可协议。转载请注明出处!并保留本声明。感谢您的阅读和支持!
-------------本文结束感谢您的阅读-------------