系统网站自助建站,南通市通州建设局网站,形象设计,wordpress幻灯片满屏分层图#xff1a; 分层图的最短路#xff1a; 又叫做 扩点最短路。不把实际位置看做是图上的点#xff0c;而是把实际位置及其状态的组合#xff0c;#xff08;一个点有若干的状态#xff0c;所以一个点会扩充出来若干点#xff09;看做是图上的点#xff0c;然后搜索…分层图 分层图的最短路 又叫做 扩点最短路。不把实际位置看做是图上的点而是把实际位置及其状态的组合一个点有若干的状态所以一个点会扩充出来若干点看做是图上的点然后搜索bfs或者dijkstra的过程不变。只是扩了点分层而已。 原理很简单核心在于如何扩点如何到达如何算距离每个题可能都不一样。注意计算扩充之后的点数。 添加链接描述 题意 二维网格只包含空房间障碍起点钥匙和对应的锁只有拿到对应的钥匙才能开对应的锁否则锁的位置和障碍没什么区别无法通过问获得所有钥匙所需要移动的最小次数相当于最短路可以上下左右移动如果无法获得所有的钥匙返回-1
边长最多是30钥匙最多是6 可以用一个数来代表这个点所获得的钥匙的状态。扩充后一共有30302^6 个点。57600个点。我感觉这道题的分层的感觉不是很强烈吧感觉更多的是状态压缩。 使用三元组 x,y,mask表示当前状态。其中(x,y)代表当前所处的位置mask 是一个二进制数长度恰好等于网格中钥匙的数量mask的第I个二进制位为1当且仅当我们已经获得了网格中的第i把钥匙。 之后使用广度优先搜索。
添加链接描述 题意 对于一个有权无向图可以将最多k条边 化为0问从起点到终点的最短路。 分层图可以看成有k1 层图代表了 使用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;vectorvectorint dis(n, vectorint(k 1, 1e9));vectorvectorint vis(n, vectorint(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_queuenode q;q.push({s,0,0});// 代表 点使用免费的次数 距离while (!q.empty()){auto ttq.top();int utt.x;int jtt.k; int costtt.y;q.pop();if (vis[u][j])continue;vis[u][j] 1;if (ue){coutcost\n;return; }for (int i h[u]; i; i ne[i]){int v to[i];// 使用 免费 的机会if (j1kdis[v][j1]dis[u][j]){dis[v][j1]dis[u][j];q.push({v,j1,dis[v][j1]});}// 不使用 免费 的机会 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 下面是 构造分层图的代码 需要构建 k1 层。每一层都有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_queuenode 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--){// 读进来 一条边将k1 层这条边都给建好cin u v ww;for (int j 0; j k; j){// 建 当前 层add(un*j, vn*j, ww);add(vn*j, un*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 ek * 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;
}
