分层图（Dijkstra实现）

什么是分层图（Layered Graph）？

分层图是一种通过构建多层图结构来处理 “状态转移” 的建模方式。具体来说，将原图复制为若干层（如 k 层），每层代表不同的状态（如允许 k 次边权修改、k 次路径变换等），层与层之间通过特定规则连边，从而将带约束的最短路问题转化为普通图的最短路问题。

特点：
- 每层图的节点和边结构与原图相似，但层间边用于表示状态切换（如使用一次 “特殊操作” 后从第 i 层转移到第 i+1 层）。
- 可处理 “允许有限次修改边权”“不同路径代价差异” 等复杂约束。
应用场景：
- 例如，在交通网络中，允许最多 k 次换乘或走高速（需额外代价），求从起点到终点的最短路径，可通过分层图建模解决。

经典例题：P4568 [JLOI2011] 飞行路线

题解：

这里为了解释分层图，给出一张解释图：

（使用 @EternalAlexander 这位dalao的OI Painter绘制）：

分层图

于是我们可以得出：

“我们可以考虑把图分成 $k+1$ 层，每往下一层，边权变成 $0$ 的边就增加 $1$ 条。编号为 $i$ 的点在第 $j$ 层的编号为 $i+j \times n$（$0 \leq i < n, 0 \leq j \leq k$）。每一层都有同样的 $n$ 个点，$m$ 条边。在层与层之间有单向边，边权为 $0$，且不能从下层到上层。对于一条边权为 $w$ 的无向边 $u \leftrightarrow v$，我们可以在第 $i=0 \sim k$ 层连无向边 $u+i \times n \leftrightarrow v+i \times n$，边权为 $w$，表示每一层里的 $u$ 和 $v$ 能互相到达，且花费的代价为 $w$。紧接着，在第 $i-1$ 层和第 $i$ 层之间连两条边权为 $0$ 的有向边 $u+(i-1) \times n \rightarrow v+i \times n$ 和 $v+(i-1) \times n \rightarrow u+i \times n$，表示可以把边 $u \rightarrow v$ 或 $v \rightarrow u$ 的边权变成 $0$，然后到下一层的 $v$ 点或 $u$ 点。建图后，$s$ 到 $t+k \times n$ 的最短路即是用完 $k$ 次机会的最少花费。最后可能没有用完 $k$ 次机会，所以到每层终点的最短路都有可能成为答案，取最小值即可。时间复杂度为 $O(mk \log(nk))$。”

——引用自洛谷题解 P4568 【[JLOI2011]飞行路线】

但是在我们实现的时候可以有：

“事实上，虽然样例可以用这种方法画图表示，但我们写代码的时候不一定要建这么多结点。只需要按照原始的输入建普通的图。考虑多维状态表示（DP）。设 $dis_{i,j}$表示当前从起点$ i $号结点，使用了$ j $次免费通行权限后的最短路径。显然，$dis $数组可以这么转移：

$$ dis_{i,j} =min\{min\{dis_{from,j−1}\},min\{dis_{from,j+w}\} $$

其中，$from$ 表示 $i$ 的父亲节点，$w $表示当前所走的边的边权。当$ j−1≥k $时，$dis_{from,j} = ∞$。事实上，这个 dp 就相当于对于每个结点的$ k+1 $个状态，想象成拆为$ k+1 $个不同的结点，每个结点之间可以相连，仿佛这张图一共有 k+1 层。对于进行 Dijkstra 算法的过程，把$ done $数组也开成二维就好，每次入队的时候分别判断能否使用免费通行权限即可。最后统计答案的时候需要统计出到最后一个结点总共$ k+1 $种状态的最短距离。”

——引用自洛谷题解 P4568 【[JLOI2011]飞行路线

代码实现：

建$k$层图版本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75


#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5+10;

struct node
{
    bool operator<(const node x) const
    {
        return w < x.w;
    }
    int v,w;
};
vector<node> vt[N];
int n,m,k;
int s,t;
bool vis[N];
int dis[N];
void solve()
{
    cin >> n >> m >> k;
    cin >> s >> t;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;cin >> u >> v >> w;
        vt[u].push_back({v,w});
        vt[v].push_back({u,w});
        for(int j=1;j<=k;j++)
        {
            vt[u+(j-1)*n].push_back({v+j*n,0});
            vt[v+(j-1)*n].push_back({u+j*n,0});
            vt[u+j*n].push_back({v+j*n,w});
            vt[v+j*n].push_back({u+j*n,w});
        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    for(int i=0;i<=n*(k+5);i++) dis[i] = INT_MAX;
    dis[s] = 0;
    pq.push({0,s});
    while(!pq.empty())
    {
        auto nod = pq.top();
        pq.pop();
        int u = nod.second;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i=0;i<(int)vt[u].size();i++)
        {
            auto [v,w] = vt[u][i];
            if(dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                pq.push({dis[v],v});
            }
        }
    }
    int ans = INT_MAX;
    for(int i=0;i<=k;i++)
        ans = min(ans,dis[t+i*n]);
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int _ = 1;
    //cin >> _;
    while(_--)
    {
        solve();
    }
    return 0;
}

状态表示实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75


#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5+10;

struct node
{
    bool operator<(const node x) const
    {
        return w > x.w;
    }
    int v,w,cnt;
};
vector<pair<int,int>> vt[N];
int n,m,k;
int s,t;
bool vis[N][12];
int dis[N][12];
void solve()
{
    cin >> n >> m >> k;
    cin >> s >> t;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        vt[u].push_back({v,w});
        vt[v].push_back({u,w});
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<=k;j++)
            dis[i][j] = INT_MAX,vis[i][j] = false;
    priority_queue<node> pq;
    dis[s][0] = 0;
    pq.push({s,0,0});
    while(!pq.empty())
    {
        auto [u,ns,cnt] = pq.top();
        pq.pop();
        if(vis[u][cnt]) continue;
        vis[u][cnt] = true;
        for(int i=0;i<(int)vt[u].size();i++)
        {
            auto [v,w] = vt[u][i];
            if(cnt < k && dis[v][cnt+1] > dis[u][cnt])
            {
                dis[v][cnt+1] = dis[u][cnt];
                pq.push({v,dis[v][cnt+1],cnt+1});
            }
            if(dis[v][cnt] > dis[u][cnt] + w)
            {
                dis[v][cnt] = dis[u][cnt] + w;
                pq.push({v,dis[v][cnt],cnt});
            }
        }
    }
    int ans = INT_MAX;
    for(int i=0;i<=k;i++)
        ans = min(ans,dis[t][i]);
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int _ = 1;
    //cin >> _;
    while(_--)
    {
        solve();
    }
    return 0;
}

例题: 小帅的车费

题目描述

小帅要去参加 ICPC 贵州省赛了，小帅的学校在 $s$ 地，省赛举办地为 $t$ 地，为了方便报销，小帅打算坐车前往。已知贵州的公交线路上有 $n$ 个站点，编号从 $0 \sim n - 1$，站点间为双向道路，每段双向道路都有对应的价格 $x$，且暑假期间公交公司给予小帅 $k$ 张优惠券，对应的折扣为 $p_1, p_2, \dots, p_k$ 。由于优惠券上有日期限制，小帅为了尽快用掉快过期的券，他会依次使用这些优惠券。每条路只能最多使用一次优惠券，当小帅对某一路段用第 $i$ 张优惠券时，该路段的价格 $x$ 将会变成：

$$ x = \left\lfloor \frac{x \cdot p_i}{100} \right\rfloor $$

请问小帅最后能否到达 $t$ 地，并计算需要的最少车费是多少？

输入格式

第一行三个整数 $n, m, k$（$1 \leq n, m \leq 10^5$, $0 \leq k \leq 10$）分别表示城市数，双向道路数，优惠券个数；第二行 $k$ 个整数 $p_1, p_2, \dots, p_k$（$0 \leq p_i \leq 99$）；第三行两个整数表示 $s, t$（$0 \leq s, t \leq n - 1$）表示出发地和到达地；最后 $m$ 行每行 3 个整数 $a, b, c$（$0 \leq a, b \leq n - 1$, $1 \leq c \leq 10^9$）表示有一条道路使站点 $a, b$ 相互连通，票价为 $c$；本题可能存在重边和自环。

输出格式

如果可以到达目的地，请输出一个整数表示所需要的最少车费；否则输出 Impossible。

Input:

Output:

1

 450

题解:

本题为最短路径变种问题，核心是在传统Dijkstra算法基础上，结合优惠券的顺序使用规则进行状态扩展。 关键思路：定义 dis[u][cnt] 表示到达节点 u 时已使用 cnt 张优惠券的最小费用。通过优先队列（小根堆）维护当前最小费用状态，每次取出最优状态后，分两种情况扩展：

不使用优惠券：直接累加当前路段原价到邻接节点；
使用下一张优惠券（若未用完）：按顺序使用第 cnt+1 张券，路段费用变为 x*p[cnt+1]/100（向下取整），更新对应状态。最终遍历所有可能的优惠券使用数量（0~k），取到达终点 t 的最小费用。若所有状态均不可达，输出 Impossible，否则输出最小费用。算法通过状态扩展覆盖所有可能的优惠券使用组合，确保找到全局最优解。
本题卡常，不能建k层图。

STD:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88


#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define INF 1e18
using namespace std;
const int N = 1e5+10;

struct node
{
    bool operator<(const node x)const
    {
        return w > x.w;
    }
    int v,w,cnt;
};
int n,m,k;
vector<pair<int,int>> vt[N];
int dis[N][11];
bool vis[N][11];
int s,t;
int p[110];

void solve()
{
    cin >> n >> m >> k;
    for(int i=1;i<=k;i++) cin >> p[i];
    cin >> s >> t;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        vt[u].push_back({v,w});
        vt[v].push_back({u,w});
    }
    priority_queue<node> pq;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=k;j++)
            dis[i][j] = INF;
    dis[s][0] = 0;
    pq.push({s,0,0});
    while(!pq.empty())
    {
        auto [u,ns,cnt] = pq.top();
        pq.pop();
        if(vis[u][cnt]) continue;
        vis[u][cnt] = true;
        for(int i=0;i<(int)vt[u].size();i++)
        {
            auto [v,w] = vt[u][i];
            if(dis[v][cnt] > dis[u][cnt] + w)
            {
                dis[v][cnt] = dis[u][cnt] + w;
                pq.push({v,dis[v][cnt],cnt});
            }
            if(cnt < k)
            {
                int ndis = w * p[cnt + 1] / 100;
                if(dis[v][cnt+1] > dis[u][cnt] + ndis)
                {
                    dis[v][cnt+1] = dis[u][cnt] + ndis;
                    pq.push({v,dis[v][cnt+1],cnt+1});
                }
            }

        }
    }
    int ans = INF;
    for (int i = 0; i <= k; i++)
        ans = min(ans, dis[t][i]);

    if (ans == INF)
        cout << "Impossible" << endl;
    else
        cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int _ = 1;
    //cin >> _;
    while(_--)
    {
        solve();
    }
    return 0;
}

分层图（含P4568 飞行路线题解）

图论（Dijkstra实现）