分层图 的尝试学习 1.0
分层图：
分层图的最短路：
又叫做 扩点最短路。不把实际位置看做是图上的点，而是把实际位置及其状态的组合，（一个点有若干的状态，所以一个点会扩充出来若干点）看做是图上的点，然后搜索bfs或者dijkstra的过程不变。只是扩了点（分层）而已。
原理很简单，核心在于如何扩点，如何到达，如何算距离，每个题可能都不一样。注意计算扩充之后的点数。
添加链接描述
题意：
二维网格，只包含空房间，障碍，起点，钥匙和对应的锁（只有拿到对应的钥匙才能开对应的锁，否则锁的位置和障碍没什么区别，无法通过）问获得所有钥匙所需要移动的最小次数（相当于最短路），可以上下左右移动如果无法；获得所有的钥匙，返回-1
边长最多是30，钥匙最多是6
可以用一个数来代表这个点所获得的钥匙的状态。扩充后一共有30302^6 个点。57600个点。我感觉这道题的分层的感觉不是很强烈吧，感觉更多的是状态压缩。
使用三元组 （x,y,mask）表示当前状态。其中(x,y)代表当前所处的位置，mask 是一个二进制数，长度恰好等于网格中钥匙的数量，mask的第I个二进制位为1，当且仅当，我们已经获得了网格中的第i把钥匙。
之后使用广度优先搜索。
添加链接描述
题意：
对于一个有权无向图，可以将最多k条边 化为0，问从起点到终点的最短路。
分层图，可以看成有k+1 层图，代表了 使用0次，1次…k次 的图。
图和图之间 通过权值为0的边连接。
进行扩点，最多1e5个点。
使用二维的dis ，和vis 数组来标记状态。（其中一维代表了使用了几次的免费）
dij求 最短路 的时候，越晚确定 到原点最短路 的点，点 到原点的 距离越远。也就是说 根据 节点 确定dis 的顺序，dis 的数值 是不减 的。（毕竟后面的点 是前面点 松弛过来的，然后边权非负）
所以，扩点求最短路。最先遇到这个点 某个状态时，这个dis 是这个点所有状态里面的最短。
所以 在 dij ，如果遇到了终点，那么不管他的使用过的免费次数是多少，直接返回。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 10;
const int M = 5e5 + 10;
int h[M], to[M], ne[M];
int w[M];
int tot = 1;
struct node
{
int x;
int k;// 使用了多少次的 免费机会
int y;// 距离
bool operator<(const node &a) const
{
return a.y < y;
}
};
void add(int u, int v, int ww)
{
to[tot] = v;
ne[tot] = h[u];
w[tot] = ww;
h[u] = tot++;
}
void solve()
{
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> dis(n, vector<int>(k + 1, 1e9));
vector<vector<int>> vis(n, vector<int>(k + 1, 0));
int s, e;
cin >> s >> e;
int u, v, ww;
while (m--)
{
cin >> u >> v >> ww;
add(u, v, ww);
add(v, u, ww);
}
auto dij = [&](int s) -> void
{
dis[s][0] = 0;
priority_queue<node> q;
q.push({s,0,0});// 代表 点，使用免费的次数 ，距离
while (!q.empty())
{
auto tt=q.top();
int u=tt.x;int j=tt.k; int cost=tt.y;
q.pop();
if (vis[u][j])
continue;
vis[u][j] = 1;
if (u==e)
{
cout<<cost<<"\n";
return;
}
for (int i = h[u]; i; i = ne[i])
{
int v = to[i];
// 使用 免费 的机会
if (j+1<=k&&dis[v][j+1]>dis[u][j])
{
dis[v][j+1]=dis[u][j];
q.push({v,j+1,dis[v][j+1]});
}
// 不使用 免费 的机会
if (dis[v][j]>dis[u][j]+w[i])
{
dis[v][j]=dis[u][j]+w[i];
q.push({v,j,dis[v][j]});
}
}
}
};
dij(s);
}
上面的那种思路，其实并没有真正的构建分层图，只是用了 增加了 一维的状态。去dp
下面是 构造分层图的代码
需要构建 k+1 层。每一层都有n 个节点
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x7fffffff
const int N = 2e5;//9e5
const int M =2e7;// 9e7
int h[N], to[M], ne[M];
int w[M], dis[N];
bool vis[N];
int tot = 1;
struct node
{
int x;
int y;
bool operator<(const node &a) const
{
return a.y < y;
}
};
void add(int u, int v, int ww)
{
to[tot] = v;
ne[tot] = h[u];
w[tot] = ww;
h[u] = tot++;
}
void dij(int s)
{
fill(dis, dis + N, inf);
dis[s] = 0;
priority_queue<node> q;
q.push({s, 0});
while (!q.empty())
{
node u = q.top();
q.pop();
if (vis[u.x])
continue;
vis[u.x] = 1;
for (int i = h[u.x]; i; i = ne[i])
{
int v = to[i];
if (dis[v] > dis[u.x] + w[i])
{
dis[v] = dis[u.x] + w[i];
q.push({v, dis[v]});
}
}
}
}
void solve()
{
int n, m, k;
cin >> n >> m >> k;
int s, e;
cin >> s >> e;
int u, v;
int ww;
while (m--)
{
// 读进来 一条边，将k+1 层，这条边都给建好
cin >> u >> v >> ww;
for (int j = 0; j <= k; j++)
{
// 建 当前 层
add(u+n*j, v+n*j, ww);
add(v+n*j, u+n*j, ww);
// 连接 这一层 和 下一层的 权值为 0的边（使用免费的票）
if (j != k)
{
add(u + n * j, v + n * (j + 1), 0);
add(v + n * j, u + n * (j + 1), 0);
}
}
}
dij(s);
int ans = inf;
for (int j = e; j <= e+k * n; j += n)
ans = min(ans, dis[j]);
cout << ans << "\n";
}
signed main()
{
std::cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
//cin >> t;
while (t--)
solve();
return 0;
}