分层图 的尝试学习 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;
}