分层图
分层图是解决最短路问题中边有多种状态的解决方式(个人理解)。
例如,k次重复走的机会。以及edu102E这样的题目。
edu102E题意是对走过的路的权和去掉一个最大权值加上一个最小权值就是该路径的权值,求最短路
notice:可以重复走
很明显一条边就有四种状态:
- 在路径中既不是最大值也不是最小值
- 在路径中是最大值不是最小值
- 在路径中不是最大值是最小值
- 在路径中是最大值也是最小值
那么对这样四种状态,我们就可以画四层图,并考虑它们之间的关系对其加边。
- $1 \text~\ n$ 第一层 为未找到最大值和最小值
- $n+1 \text~\ 2n$ 第二层 为找到了最大值但未找到最小值
- $2n+1 \text~\ 3n$ 第三层 为找到了最小值但未找到最大值
- $3n+1 \text~\ 4n$ 第四层 为找到了最大最小值
1->2
$add(a,b+n,0)$
$add(a+n,b,0)$
1->3
$add(a,b+2n,2c)$
$add(a,b+2n,2c)$
1->4
$add(a,b+3n,c)$
$add(a,b+3n,c)$
2->4
$add(a+n,b+3n,2c)$
$add(b+n,a+3n,2c)$
3->4
$add(a+2n,b+3n,0)$
$add(b+2n,a+3n,0)$
最后就普通的用堆优化的dij跑一下就行了
/*
Problem Name:Minimum Path
algorithm tag:最短路
*/
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int n, m;
vector<pii> g[N * 4];
ll dist[N * 4];
void dij()
{
priority_queue<pli, vector<pli>, greater<pli>> heap;
for (int i = 1; i <= 4 * n; i++)
dist[i] = 1e18;
heap.push({0, 1});
dist[1] = 0;
while (heap.size()) {
ll w = heap.top().first;
int u = heap.top().second;
heap.pop();
if (w > dist[u])
continue;
for (auto v : g[u]) {
if (v.second + w < dist[v.first]) {
dist[v.first] = (ll)v.second + w;
heap.push({dist[v.first], v.first});
}
}
}
for (int i = 3 * n + 2; i <= 4 * n; i++) {
cout << dist[i] << " ";
}
cout << endl;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
g[a + n].push_back({b + n, c});
g[b + n].push_back({a + n, c});
g[a + 2 * n].push_back({b + 2 * n, c});
g[b + 2 * n].push_back({a + 2 * n, c});
g[a + 3 * n].push_back({b + 3 * n, c});
g[b + 3 * n].push_back({a + 3 * n, c});
g[a].push_back({b + n, 0});
g[b].push_back({a + n, 0});
g[a].push_back({b + 2 * n, 2 * c});
g[b].push_back({a + 2 * n, 2 * c});
g[a].push_back({b + 3 * n, c});
g[b].push_back({a + 3 * n, c});
g[a + n].push_back({b + 3 * n, 2 * c});
g[b + n].push_back({a + 3 * n, 2 * c});
g[a + 2 * n].push_back({b + 3 * n, 0});
g[b + 2 * n].push_back({a + 3 * n, 0});
}
dij();
}