[学习笔记]分层图最短路

分层图的概念

分层图最短路，听名字就知道他和其他最短路不一样，实际也确实如此，可以解决一些普通最短路无法解决的问题。

比如有 \(n\) 个点 \(m\) 条带权无向边，可以将 \(k\) 条边进行某些操作，然后求出从 \(1\) 到 \(n\) 的最短路，此时即可使用分层图。

例题

例题 1 P4568 [JLOI2011] 飞行路线

P4568 [JLOI2011] 飞行路线

简化题意

有 \(n\) 个点 \(m\) 条带权无向边，可以将 \(k\) 条边的边权变为 \(0\)，求从 \(s\) 到 \(t\) 的最短路。

分析

这就是开头所说的例子，设 \(dis_{i, j}\) 为将 \(j\) 条边的边权变为 \(0\) 的情况的最短路，然后正常跑 dijkstra，

答案为 \(\sum\limits_{i=1}^{k}\min(dis_{t, i})\)。

AC 代码

/*Code By Manipula*/
#include <bits/stdc++.h>
// #define Fileopen
#pragma GCC optimize(2)
#define INF 0x3f3f3f3f
#define int long long
#define swap(x, y) x ^= y ^= x ^= y
#define sqrt(n) pow(n, 0.5)
#define sort stable_sort
#define mk(x, y) make_pair(x, y)
#define mst(arr, num) memset(arr, num, sizeof(arr))
#define endl '\n'
using namespace std;
const int N = 1e4 + 5;
struct Edge{
	int v, w, nxt;
}edge[N * 10];
struct Queue{
	int u, k, w;
	bool operator < (const Queue a) const{
		return w > a. w;
	}
};
priority_queue<Queue> q;
int head[N], dis[N][15], vis[N][15];
int n, m, num, k, ans = INF;
void add(int u, int v, int w){edge[++num] = (Edge){v, w, head[u]}; head[u] = num;}
void dijkstra(int s)
{
	mst(dis, INF);
	dis[s][0] = 0; q.push((Queue){s, 0, 0});
	while (!q.empty())
	{
		int u = q.top().u, nowk = q.top().k; q.pop();
		if (vis[u][nowk])continue; vis[u][nowk] = 1;
		for (int i = head[u]; i; i = edge[i].nxt)
		{
			int v = edge[i].v, w = edge[i].w;
			if (nowk < k && dis[v][nowk + 1] > dis[u][nowk])
			{
				dis[v][nowk + 1] = dis[u][nowk];
				q.push((Queue){v, nowk + 1, dis[v][nowk + 1]});
			}
			if (dis[v][nowk] > dis[u][nowk] + w)
			{
				dis[v][nowk] = dis[u][nowk] + w;
				q.push((Queue){v, nowk, dis[v][nowk]});
			}
		}
	}
}
signed main()
{
	#ifdef Fileopen
		freopen(".in", r, stdin);
		freopen(".out", w, stdout);
	#endif
	int s, t;
	cin >> n >> m >> k >> s >> t;
	for (int i = 1, u, v, w; i <= m; i++)
	{
		cin >> u >> v >> w;
		add(u, v, w); add(v, u, w);
	}
	dijkstra(s);
	for (int i = 0; i <= k; i++)ans = min(ans, dis[t][i]);
	cout << ans;
	return 0;
}

例题 2 P4822 [BJWC2012] 冻结

P4822 [BJWC2012] 冻结

简化题意

有 \(n\) 个点 \(m\) 条带权无向边，可以将 \(k\) 条边的边权变为原来的一半，求从 \(1\) 到 \(n\) 的最短路。

分析

与上一题的想法大致是一样的，只不过上一题的变为 \(0\) 变成了变为原来的一半，总体代码差不多，但仍然给一下代码。

AC 代码

/*Code By Manipula*/
#include <bits/stdc++.h>
// #define Fileopen
#pragma GCC optimize(2)
#define INF 0x3f3f3f3f
#define int long long
#define swap(x, y) x ^= y ^= x ^= y
#define sqrt(n) pow(n, 0.5)
#define sort stable_sort
#define mk(x, y) make_pair(x, y)
#define mst(arr, num) memset(arr, num, sizeof(arr))
#define endl '\n'
using namespace std;
const int N = 1e4 + 5;
struct Edge{
	int v, w, nxt;
}edge[N * 10];
struct Queue{
	int u, k, w;
	bool operator < (const Queue a) const{
		return w > a. w;
	}
};
priority_queue<Queue> q;
int head[N], dis[N][55], vis[N][55];
int n, m, num, k, ans = INF;
void add(int u, int v, int w){edge[++num] = (Edge){v, w, head[u]}; head[u] = num;}
void dijkstra(int s)
{
	mst(dis, INF);
	dis[s][0] = 0; q.push((Queue){s, 0, 0});
	while (!q.empty())
	{
		int u = q.top().u, nowk = q.top().k; q.pop();
		if (vis[u][nowk])continue; vis[u][nowk] = 1;
		for (int i = head[u]; i; i = edge[i].nxt)
		{
			int v = edge[i].v, w = edge[i].w;
			if (nowk < k && dis[v][nowk + 1] > dis[u][nowk] + w / 2)
			{
				dis[v][nowk + 1] = dis[u][nowk] + w / 2;
				q.push((Queue){v, nowk + 1, dis[v][nowk + 1]});
			}
			if (dis[v][nowk] > dis[u][nowk] + w)
			{
				dis[v][nowk] = dis[u][nowk] + w;
				q.push((Queue){v, nowk, dis[v][nowk]});
			}
		}
	}
}
signed main()
{
	#ifdef Fileopen
		freopen(".in", r, stdin);
		freopen(".out", w, stdout);
	#endif
	cin >> n >> m >> k;
	for (int i = 1, u, v, w; i <= m; i++)
	{
		cin >> u >> v >> w;
		add(u, v, w); add(v, u, w);
	}
	dijkstra(1);
	for (int i = 0; i <= k; i++)ans = min(ans, dis[n][i]);
	cout << ans;
	return 0;
}