最短路——分层图问题
这里以一道题目为例
题目描述
Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 \(n\) 个城市设有业务，设这些城市分别标记为 \(0\) 到 \(n-1\)，一共有 \(m\) 种航线，每种航线连接两个城市，并且航线有一定的价格。
Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 \(k\) 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？
输入格式
第一行三个整数 \(n,m,k\)，分别表示城市数，航线数和免费乘坐次数。
接下来一行两个整数 \(s,t\)，分别表示他们出行的起点城市编号和终点城市编号。
接下来 \(m\) 行，每行三个整数 \(a,b,c\)，表示存在一种航线，能从城市 \(a\) 到达城市 \(b\)，或从城市 \(b\) 到达城市 \(a\)，价格为 \(c\)。
输出格式
输出一行一个整数，为最少花费。
样例输入
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
样例输出
8
数据规模与约定
对于 \(30\%\) 的数据，\(2 \le n \le 50\)，\(1 \le m \le 300\)，\(k=0\)。
对于 \(50\%\) 的数据，\(2 \le n \le 600\)，\(1 \le m \le 6\times10^3\)，\(0 \le k \le 1\)。
对于 \(100\%\) 的数据，\(2 \le n \le 10^4\)，\(1 \le m \le 5\times 10^4\)，\(0 \le k \le 10\)，\(0\le s,t,a,b < n\)，\(a\ne b\)，\(0\le c\le 10^3\)。
另外存在一组 hack 数据。
区别与一般的单图问题，这道题中我们需要考虑可以免费坐飞机的航线
相当于每个节点都存在一个状态，即到这个节点还能免费坐飞机的次数
拥有相同状态的节点共同组成一张图
所以需要对寻路的方式进行部分修改，这里采用优先队列的Dijkstra最短路算法
struct node
{
int dw, dnode, cnt;
bool operator<(const node& a)const {
return dw > a.dw;
}
};
构造优先队列 priority_queue 使用的结构体，并重载小于号
其中存储了这个节点的编号dnode ，节点到起始点的距离 dw ，以及当前节点使用的免费次数 cnt
int dis[20010][12];
bool vis[20010][12];
同样的，记录最短距离的 dis 和记录访问节点的 vis 数组都需要根据状态的不同来进行分层操作
void dijkstra(int st) {
init();
q.push({ 0, st, 0 });
dis[st][0] = 0;
while (q.size())
{
const node ttop = q.top();
q.pop();
if (vis[ttop.dnode][ttop.cnt]) continue;
vis[ttop.dnode][ttop.cnt] = 1;
for (auto it = e[ttop.dnode].begin(); it != e[ttop.dnode].end(); it++) {
if (ttop.cnt < k&& dis[it->v][ttop.cnt + 1] > dis[ttop.dnode][ttop.cnt]) {
dis[it->v][ttop.cnt + 1] = dis[ttop.dnode][ttop.cnt];
q.push({ dis[it->v][ttop.cnt + 1],it->v,ttop.cnt + 1 });
}
if (dis[it->v][ttop.cnt] > dis[ttop.dnode][ttop.cnt] + it->w) {
dis[it->v][ttop.cnt] = dis[ttop.dnode][ttop.cnt] + it->w;
q.push({ dis[it->v][ttop.cnt],it->v,ttop.cnt });
}
}
}
}
除了松弛操作外，多层图和单图的源码几乎相同，都采用了优先队列贪心来找当前最优的节点
在松弛操作内，我们需要考虑当前的节点能否使用免费的次数，免费后是不是最优
- 当前的节点可以免费
if (ttop.cnt < k&& dis[it->v][ttop.cnt + 1] > dis[ttop.dnode][ttop.cnt]) {//判断是不是最优
dis[it->v][ttop.cnt + 1] = dis[ttop.dnode][ttop.cnt];//如果能更新最短路径，那就更新
q.push({ dis[it->v][ttop.cnt + 1],it->v,ttop.cnt + 1 });//将更新后的节点放入队列，注意状态也要更新
}
- 当前的节点不能免费或不采取免费
if (dis[it->v][ttop.cnt] > dis[ttop.dnode][ttop.cnt] + it->w) {//判断能否更新
dis[it->v][ttop.cnt] = dis[ttop.dnode][ttop.cnt] + it->w;
q.push({ dis[it->v][ttop.cnt],it->v,ttop.cnt });//放入更新后的节点
}
Dijkstra寻路结束后，我们遍历一遍终点节点的所有状态，找到一个最小的dis[ed][i]，即最优解
int ans = 1e9;
for (int i = 0; i <= k; i++) ans = min(ans, dis[ed][i]);
图上的每一个节点都有向下层的可联通节点前进的无权边（免费）
上图以 \(0\) 号节点为例，它可以通过免费次数构建出来的边向下层图移动，直到免费次数用尽
总而言之，解决分层图的关键就在建图，需要正确地通过不同的状态构造出图
完整代码：
#include <vector>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#define streampreset() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
struct edge
{
int v, w;
};
struct node
{
int dw, dnode, cnt;
bool operator<(const node& a)const {
return dw > a.dw;
}
};
int n, m, k;
int st, ed;
vector<edge> e[50010];
priority_queue<node> q;
int dis[20010][12];
bool vis[20010][12];
void insert(int u, int v, int w) {
e[u].push_back({ v,w });
}
void init(void) {
memset(dis, 0x3f, sizeof dis);
}
void dijkstra(int st) {
init();
q.push({ 0, st, 0 });
dis[st][0] = 0;
while (q.size())
{
const node ttop = q.top();
q.pop();
if (vis[ttop.dnode][ttop.cnt]) continue;
vis[ttop.dnode][ttop.cnt] = 1;
for (auto it = e[ttop.dnode].begin(); it != e[ttop.dnode].end(); it++) {
if (ttop.cnt < k&& dis[it->v][ttop.cnt + 1] > dis[ttop.dnode][ttop.cnt]) {
dis[it->v][ttop.cnt + 1] = dis[ttop.dnode][ttop.cnt];
q.push({ dis[it->v][ttop.cnt + 1],it->v,ttop.cnt + 1 });
}
if (dis[it->v][ttop.cnt] > dis[ttop.dnode][ttop.cnt] + it->w) {
dis[it->v][ttop.cnt] = dis[ttop.dnode][ttop.cnt] + it->w;
q.push({ dis[it->v][ttop.cnt],it->v,ttop.cnt });
}
}
}
}
int main()
{
streampreset();
cin >> n >> m >> k >> st >> ed;
int u, v, w;
for (int i = 0; i < m; i++) {
cin >> u >> v >> w;
insert(u, v, w);
insert(v, u, w);
}
dijkstra(st);
int ans = 1e9;
for (int i = 0; i <= k; i++) ans = min(ans, dis[ed][i]);
cout << ans;
return 0;
}