常见建图技巧

负环

• 在图中存在一条环路，其所有边权之和小于 $0$。
• 记为：若环路顶点序列为 $v_1 \to v_2 \to \cdots \to v_k \to v_1$，则

\[ \sum_{i=1}^{k} w(v_i, v_{i+1}) < 0. \]

若存在负权环，则可以无限次沿该环 跑 下去，总路径长度不断减小，无法收敛到一个最小值。

---

Bellman-Ford 检测负环

• Bellman–Ford 最短路算法过程中，最多需要 $n-1$ 轮松弛即可收敛。
• 若进行第 $n$ 轮松弛时仍有边被松弛，则说明图中存在从源点可达的负环。

注意： 检测到的是 从起点 s 出发可达的负环，可能无法检测到其他连通分量的负环。

时间复杂度：$O(nm)$，空间复杂度：$O(n+m)$。

void bellman_ford(int s)
{
    for (int i = 1; i <= n; i++) dis[i] = 1e9;
    dis[s] = 0;
    for (int t = 1; t < n; t++) // 没有负边权，松弛 n - 1 次即可
    {
        for (int i = 1; i <= m; i++)
        {
            int u = e[i].u, v = e[i].v, w = e[i].w;
            if (dis[u] == 1e9) continue; // 避免假松弛
            if (dis[v] > dis[u] + w) // 判断是否会进行松弛
            {
                dis[v] = dis[u] + w;
            }
        }
    }
    for (int i = 1; i <= m; i++)
    {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if (dis[u] == 1e9) continue;  // 避免假松弛
        if (dis[v] > dis[u] + w)
        {
            cout << "存在一个从起点 s 出发的负环";
        }
    }
}

举例说明假松弛

如图所示，显然不存在从 $1$ 出发可达的负环。但我们初始化数组时会初始化 $dis[3]=dis[4]=10^9$。

导致 $dis[4]>dis[3]+(-10)$ 判断成立，这实际是一个 假松弛。进而判定负环存在这是不对的。

---

SPFA 检测负环

SPFA 思想

用队列维护 待松弛 节点，每次取队头 $u$，尝试松弛所有出边 $(u\to v,w)$。

• 若 $dis[u]+w<dis[v]$，则更新 $dis[v]$，并将 $v$ 入队（若尚未在队中）。

负环检测

• 维护数组 $\mathrm{cnt}[v]$，表示当前最短路到 $v$ 所用边数；
  • 初始 $\mathrm{cnt}[S]=0$，其余也都设为 0。
• 每次成功松弛 $(u\to v)$ 时：

\[ \mathrm{cnt}[v] \;=\; \mathrm{cnt}[u]+1. \]

• 若 $\mathrm{cnt}[v]\ge n$（点数），则说明存在一条可从 $S$ 达到的负环

#include <bits/stdc++.h>
using namespace std;
int n, m, dis[2005], cnt[2005];
bool vis[2005];
vector<pair<int, int>> e[2005];
int spfa(int s)
{
    for (int i = 1; i <= n; i++)
    {
        dis[i] = 1e9;
        vis[i] = 0;
        cnt[i] = 0;
    }
    dis[s] = 0, vis[s] = 1, cnt[s] = 0;
    queue<int> q;
    q.push(s);
    while (q.size())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (auto it : e[u])
        {
            int v = it.first, w = it.second;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) return -1;
                if (!vis[v])
                {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return 1;
} 
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) e[i].clear();
        while (m--)
        {
            int u, v, w;
            cin >> u >> v >> w;
            if (w >= 0)
            {
                e[u].push_back({v, w});
                e[v].push_back({u, w});
            }
            else
            {
                e[u].push_back({v, w});
            }
        }
        int res = spfa(1);
        if (res == -1) cout << "YES\n";
        else cout << "NO\n";
    } 
    return 0;
}

---

例题：[USACO09NOV] Job Hunt S

题意： 牛在每个城市最多赚 $D$，需移动才能继续挣钱。路径无成本，航线需花费 $T$，可用未来收入支付。 问：无限时间内最大可赚多少？若无限，输出 $-1$。

思路： 本题属于既有点权又有边权，首先需要统一为边权。

• 普通道路：到达城市可赚 $D$，等价边权 $+D$.
• 航线：到达城市赚 $D$ 花费 $T$，等价边权 $D - T$.

于是问题化为：在有向图上求 最长路径，存在 正权环 则可以无限挣钱。

最长路松弛

\[ \text{松弛操作：} \quad \text{dis}[v] \leftarrow \max\bigl(\text{dis}[v],\;\text{dis}[u]+w\bigr). \]

最多 $C-1$ 轮可收敛。 第 $C$ 轮若仍发生松弛，则存在正权环 $\to$ 输出 $-1$.

注意本题起点的值直接初始化为 $D$，直接挣到 $D$ 美元。

#include <bits/stdc++.h>
using namespace std;
int d, p, c, f, s, dis[225];
struct edge
{
    int u, v, w;
};
vector<edge> e; 
int bellman_ford(int s)
{
    for (int i = 1; i <= c; i++) dis[i] = -1e9;
    dis[s] = d; // 在起点直接赚钱
    for (int i = 1; i < c; i++)
    {
        for (auto it : e)
        {
            int u = it.u, v = it.v, w = it.w;
            if (dis[u] == -1e9) continue;
            if (dis[v] < dis[u] + w)
            {
                dis[v] = dis[u] + w;
            }
        }
    } 
    for (auto it : e)
    {
        int u = it.u, v = it.v, w = it.w;
        if (dis[u] == -1e9) continue;
        if (dis[v] < dis[u] + w)
        {
            return -1;
        }
    }
    int mx = -1e9;
    for (int i = 1; i <= c; i++) mx = max(mx, dis[i]);
    return mx;
} 
int main()
{
    cin >> d >> p >> c >> f >> s;
    for (int i = 1; i <= p; i++)
    {
        int u, v;
        cin >> u >> v;
        e.push_back({u, v, d}); // 点权转化为边权，走过去就赚取 d 美元
    }
    for (int i = 1; i <= f; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e.push_back({u, v, d - w}); // 航线扣 w 美元，因此边权为 d - w
    }
    cout << bellman_ford(s);
    return 0;
}

---

总结

• Bellman–Ford/SPFA：可支持任意正负边，最短路和最长路均可。
• Floyd：可支持任意正负边，最短路和最长路均可，但时间复杂度是 $O(n^3)$。
• 只适用于 全正权最短路 或 全负权最长路，不支持混合情形。

Dijkstra 不适于正权最长路

• 最长路无 贪心子结构，每次选最优并不安全。

可以参考如下反例：

若用 Dijkstra 思想（每次取当前最大的 dis），错误地得到：

\[ dis_1=0,\; dis_2=4,\; dis_3=4,\; dis_4=1. \]

实际最长路径是

\[ 1 \to 4 \to 3 \to 2 = 1 + 3 + 2 = 6. \]

---

建图技巧

反图

给定有向图 $G=(V,E)$，其反图 $G'=(V,E')$ 中，每条 $u\to v\in E$ 在 $G'$ 中变为 $v\to u\in E'$。

当我们需要多次求 $\,i\to x$ 的最短路（每个 $i$ 都当源点）时，直接跑 $n$ 次 Dijkstra/SPFA 代价太高。

构造反图后，只需以 $x$ 为源跑一次最短路，即可得到原图中所有 $i\to x$ 的最短距离。

---

例题：[USACO07FEB] Cow Party

题意： $n$ 头牛要去编号为 $x$ 的农场参加派对，派对结束后再各自回家。农场间有 $m$ 条有向路径，路径长度为正。每头牛去和回都走最短路，求这 $n$ 条「往返」路径中最长的一条。

即求解：

\[ \max_{1\le i\le n}\bigl(\,dis_{i\to x} + dis_{x\to i}\bigr). \]

思路：

• 正向图 $\,G$：从 $x$ 出发跑一次 Dijkstra，得所有 $dis_{x\to i}$.
• 反向图 $\,G'$：将每条边反向后，从 $x$ 出发跑一次 Dijkstra，得所有 $dis'{x\to i}=dis{i\to x}$.
• 合并答案：$\displaystyle \max_{i}\bigl(dis'{x\to i}+dis{x\to i}\bigr).$

具体实现

• 边权皆正，使用 \alert{堆优化 Dijkstra}，复杂度 $O(m\log n)$。
• 反图存储：另一组邻接表 $\texttt{revG}$。
• 使用自定义函数，将数组传入参数减少重复代码。

参考代码

void dijkstra(int s, int dis[], vector<pii> e[])
{
    for (int i = 1; i <= n; i++) dis[i] = 1e9;
    dis[s] = 0;
    vector<bool> vis(n + 1, false);
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto it : e[u])
        {
            int v = it.first, w = it.second;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dijkstra(s, dis1, e);
    dijkstra(s, dis2, g);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dis1[i] + dis2[i]);
    cout << ans;   
    return 0;
}

---

虚拟节点

在原图之外新建一些 辅助节点，并用零权或特殊权值的边将它们连入图中，以便一次跑最短/最长路即可解决多个源点或多个汇点的问题。

• 常见场景：多源最短路 $S$ 集合到 $T$ 集合的最短路
• 关键：把 集合 统一为一个点，再做一次常规图算法。

示例：多源 $\to$ 多汇最短路

暴力做法：对每个源点跑一次 Dijkstra/SPFA，取最小值。复杂度 $O(|S|\,(E\log V))$。

用虚拟节点优化

• 新建 虚拟源 $0$，对每个原始源点 $s_i$ 加边 $0\to s_i$，权值 $0$。
• 新建 虚拟汇 $n+1$，对每个原始汇点 $t_i$ 加边 $t_i\to n+1$，权值 $0$。
• 在新图上求从 $0\to n+1$ 的最短路等价于原图。

---

例题：CF938D — Buy a Ticket

题意： 无向图上每个城市 $i$ 参加演唱会需支付门票 $a_i$，同时来回路程费用为 $2\cdot \mathrm{dist}(i,j)$。 求每个城市的最小总花费。

暴力：对每个 $i$ 跑一次最短路 $O(n\,m\log m)$ 会 TLE。

思路：

本题属于既有点权也有边权，这类题通常是要统一处理的。这里需要借助一个虚拟源点来将点权也转化为边权。

巧用“虚拟源”

把门票花费 $a_j$ 看作 从源出发 的单程成本：

\[ \underbrace{0}_{\text{源}\to i} \;\;\xrightarrow{a_i}\;\; \]

即建立一个超级源点 $0$，向每个点 $i$ 连接一条边，长度为 $a_i$。

• 有向边即可。无向边意义不大。

再来考虑往返路程，由于是无向图的缘故。走过去和走回来的路径必然相同，因此可以把每条边的长度直接乘以 $2$。

具体实现

• 新建节点 $0$，对每个城市 $j$ 加边 $0\to j$，权值 $a_j$.
• 原图每条无向边 ${u,v}$ 替为两条有向边 $u\to v$ 和 $v\to u$，权值均为 $2w$。
• 从 $0$ 出发跑一次 Dijkstra，结果 $dis[j]$ 即为答案。

核心代码

vector<vector<pair<int, long long>>> G(n + 1);
for (int i = 1; i <= m; i++)
{
    int u, v;
    long long w;
    cin >> u >> v >> w;
    G[u].push_back({v, 2 * w});
    G[v].push_back({u, 2 * w});
}
// 虚拟源 0
for (int i = 1; i <= n; i++)
{
    G[0].push_back({i, a[i]});
}

---

例题：[W1] 团

题意： 有一张 $n$ 个节点的无向边带权图。它的边很多，用这个方法表示：

• 有 $k$ 个集合；第 $i$ 个集合可以表示为 $S_i={(T_1,W_1),(T_2,W_2),\dots,(T_{|S_i|},W_{|S_i|})}$。
• 对于任何两对 $(T_i,W_i),(T_j,W_j)$ 在同一个集合里面，图中会形成一条连 $T_i$ 和 $T_j$ 的边，边权为 $W_i+W_j$。

请对于所有节点 $i$ 找到 $1$ 到 $i$ 的最短路，即从 $1$ 到 $i$ 的边权和最小的简单路径。

暴力建图显然时间和空间均无法承受。

虚拟节点思路

• 为每个集合 $S_i$ 新建一个 虚拟节点 $v_i$；
• 对集合内每个原节点 $u\in S_i$ 加一条无向边 ${u,v_i}$，权重为给定的 $W_u$；
• 这样就只用了 $\sum_i |S_i|$ 条边，且通过中转 $v_i$ 可实现任意两点互通。

示例

原始做法：集合 $S={u_1,u_2,\ldots,u_k}$ 内两两连边，一共连接 $\binom{k}{2}=\frac{k\cdot (k-1)}{2}\text{ 条边}$

优化后：增加一个虚拟节点 $v_i$，每个点向虚拟节点 $v_i$ 连一条无向边，只需要 $2k$ 条边。

// 假设原节点编号 1..N，集合编号 1..K
int N, K;
vector<vector<pair<int, int>>> G(n + K + 1);
// 对每个集合 i（i=1..K）：
for (int i = 1; i <= K; i++) 
{
    int m;
    cin >> m; // 当前集合大小
    int vi = n + i;  // 虚拟节点编号
    for (int i = 1; i <= m; i++) 
    {
        int u, w;
        cin >> u >> w;
        G[u].push_back({vi, w});
        G[vi].push_back({u, w});
    }
}
// 之后直接在 G 上跑 Dijkstra 最短路算法

---

拆点

拆点是一种常用于图论建模的技术，核心思想类似于动态规划 —— 在图的节点上附加状态信息，扩展为多维状态图。通常应用于以下场景：

• 节点在不同状态下具有不同的含义或权值。
• 边的转移会影响某种资源（如次数、时间、路径长度等）。

例题：CSP-J 2019 加工零件

题意： 给定一个 $n$ 个点 $m$ 条边的无向图，有 $q$ 组询问，每次询问给定一个点 $a$，问从 $a$ 出发是否可以经过恰好 $L$ 条边到达点 $1$。

转化：由于是无向图每组询问可以看成从 $1$ 出发恰好经过 $L$ 条边是否可以到达点 $a$。

暴力：

• 定义 dfs(u, k) 的搜索函数，其中 $u$ 代表当前结点编号，$k$ 代表目前已经走了几条边。
• 边界：当 $u$ 等于 $a$ 且 $k$ 为 $0$ 就证明可以。
• 每次搜索遍历邻点 $v$，执行 dfs(v, k - 1) 即可。
• 每次询问调用 dfs(1, L) 即可。

void dfs(int u, int k)
{
    if (flag) return ;
    if (u == a && k == 0)
    {
        flag = 1;
        return ;
    }
    for (auto v : e[u])
    {
        if (k > 0)
        {
            dfs(v, k - 1);
        }
    }
}

优化

结论：如果从 $1$ 出发经过 $L$ 条边可以到达点 $a$，那么经过 $L+2,L+4,\dots$ 条边都可以到达点 $a$。

• 只需要挑选一条边每次来回走一遍让距离加 $2$ 即可。

故而可以预处理出从 $1$ 出发到达每个点经过奇数条边和偶数条边的最短路，对于每一组询问的点 $a,L$，只需要判断在和 $L$ 奇偶性相同的情况下，最短路距离是否小于等于 $L$ 即可。

由于边权均为 $1$，因此使用 BFS 即可处理最短路。

将每个点拆出两种状态，使用 dis[i][j] 存到达点 $i$ 经过奇数还是偶数条边的最短路（$j$ 取 $0$ 代表偶数，取 $1$ 代表奇数）。

• 特别的判重数组也需要多开一维，奇数点和偶数点需要分开来避免重复入队。
• 队列当中不仅需要记录每个点的编号，也得记录每个点的状态。
  • 设队头为 $u$ 它的状态是 $x$，遍历它的邻点 $v$
  • 则 $dis_{v,x\oplus 1}=dis_{u,x}+1$ 然后将 $v$ 和 $v$ 的状态继续入队。

对于每组询问记得特判若无法到达某个点需要输出 $-1$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, q, dis[N][2];
bool vis[N][2];
vector<int> e[N];
void bfs()
{
    queue<pair<int, int>> q;
    q.push({1, 0}); // 初始在 1 经过 0 条边对应偶数状态入队
    dis[1][0] = 0, vis[1][0] = 1;
    while (q.size())
    {
        auto now = q.front(), q.pop();
        int u = now.first, x = now.second;
        for (auto v : e[u])
        {
            if (!vis[v][x ^ 1])
            {
                vis[v][x ^ 1] = 1, dis[v][x ^ 1] = dis[u][x] + 1;
                q.push({v, x ^ 1});
            }
        }
    }
}
int main()
{
    cin >> n >> m >> q;
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    while (q--)
    {
        int a, L;
        cin >> a >> L;
        if (!vis[a][L & 1]) // 对应状态的 a 没有访问过 
        {
            cout << "No\n";
            continue;
        }
        if (dis[a][L & 1] <= L) cout << "Yes\n";
        else cout << "No\n";
    }
}

---

例题：[JLOI2011] 飞行路线

题意： 给定一张 $n$ 个点、$m$ 条边的无向图。你可以在路径中至多选择 $k$ 条边免费通过。目标：从起点 $s$ 到终点 $t$ 的最短路径代价。

错误示例 尝试对代价最大的 $k$ 条边进行 贪心 免费处理是错误的，因为这些边不一定出现在最短路径中。

状态设计与建模

• 状态定义：将每个节点拆分为 $k+1$ 个状态，表示当前还剩多少次免费机会：

\[ dis_{i,j} = \text{从起点出发，到达点 }\ i \text{ 且剩余 }\ j \text{ 次免费机会的最短路径} \]

• 状态转移，假设当前在点 $u$，剩余 $t$ 次免费机会，欲走向点 $v$，边权为 $w$：

  • 不使用免费机会：$dis_{v,t} = \min(dis_{v,t}, dis_{u,t} + w)$
  • 使用一次免费机会（若 $t > 0$）：$dis_{v,t-1} = \min(dis_{v,t-1}, dis_{u,t})$

• 答案与实现细节

  • 最终答案：$\displaystyle \min_{j=0}^{k} dis_{t,j}$，不要求用完所有免费机会。
  • 优先队列中记录三元组 $(d, u, j)$，分别为当前距离、节点编号、剩余免费次数。
• $\texttt{vis}$ 与 $\texttt{dis}$ 数组需开二维。
• 使用免费机会前必须判断 $t > 0$。
• 不同状态视为不同点，需分别松弛。

代码实现

时间复杂度：$O(m\cdot k\cdot \log{(m\cdot k)})$

void dijkstra(int s, int t)
{
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= t; j++)
            dis[i][j] = 1e9;
    dis[s][t] = 0; // 在起点 s 还有 t 次免费的最短路为 0
    priority_queue<array<int, 3>, vec<array<int, 3>>, greater<array<int, 3>>> q; // 小根堆
    q.push({0, s});
    while (!q.empty())
    {
        auto [d, u, k] = q.top(); // C++17 语法结构化绑定
        q.pop();
        if (vis[u][k]) continue;
        vis[u][k] = 1;
        for (auto it : e[u])
        {
            int v = it.first, w = it.second;
            if (dis[v][k] > dis[u][k] + w) // 不免费
            {
                dis[v][k] = dis[u][k] + w;
                q.push({dis[v][k], v, k});
            }
            if (k && dis[v][k - 1] > dis[u][k] + 0) // 选择免费，边权为 0
            {
                dis[v][k - 1] = dis[u][k] + 0;
                q.push({dis[v][k - 1], v, k - 1});
            }
        }
    }
}

---

分层图

在上一题中，我们提到将一个节点拆分为 $k+1$ 种状态，相当于从图论视角构造出一个包含 $n(k+1)$ 个 虚拟节点 的新图。

这种方法被称为：分层图建模（Layered Graph Modeling）。

编号方式

假设原图共有 $n$ 个节点，每个节点拆分为 $k+1$ 层：

\[ \text{第 }\ i \text{ 个节点在第 }\ j \text{ 层的编号为 }\ i + j \times n \]

例如：原图中节点 $1$ 在 $k+1$ 层中的编号分别为 $1,\ n+1,\ 2n+1,\ \dotsc,\ kn+1$。

---

结构图示

我们可以将原图 复制 $k$ 次，构造出 $k+1$ 层结构的分层图：

• 第 0 层：表示未使用任何免费机会。
• 第 1 层：表示使用 1 个免费机会。
• 第 2 层：表示使用 2 个免费机会。
• 以此类推。

跨层连边方式

在构建分层图时，层与层之间也要建立转移边，模拟 使用一次免费机会 的行为。

假设原图中存在一条无向边 $(u,v)$，长度为 $w$，我们在分层图中对应连边：

• 不使用免费机会：在每层 $j$ 中，连接 $u + jn \to v + jn$ 和 $v + jn \to u + jn$，边权为 $w$。
• 使用一次免费机会：连接 $u + jn \to v + (j+1)n$ 和 $v + jn \to u + (j+1)n$，边权为 $0$（前提是 $j < k$）。

代码实现

for (int j = 0; j <= k; j++)
{
    // 层内正常连边
    e[j * n + u].push_back({j * n + v, w}); // 第 j 层的 u 连向第 j 层的 v 长度为 w
    e[j * n + v].push_back({j * n + u, w}); // 第 j 层的 v 连向第 j 层的 u 长度为 w
    if (j > 0) // 第 j - 1 层连向第 j 层
    {
        e[(j - 1) * n + u].push_back({j * n + v, 0}); // 第 j - 1 层的 u 连向第 j 层的 v 长度为 0
        e[(j - 1) * n + v].push_back({j * n + u, 0}); // 第 j - 1 层的 v 连向第 j 层的 u 长度为 0
    }
}

---

实现总结：代码层面注意事项

• 数组大小注意：总节点数为 $(k+1) \times n$，$\texttt{dis}$、$\texttt{vis}$ 等数组需按此大小定义。
• Dijkstra 模板：在构建好分层图后，最短路算法可以直接套用 Dijkstra 模板，状态二元组为 $(d, u)$，其中 $u$ 是展开后的编号。
• 终点枚举：由于终点可能出现在任意一层，最终答案应为：

\[ \texttt{ans} = \min_{i=0}^{k} \texttt{dis}[i \times n + \texttt{ed}] \]

• 分层图是 拆点思想 在图论建模中的具体实现手段，适用于附加资源（如免费次数、体力、换乘等）的建模。
• 每一层代表一种资源消耗状态，层间边的设计必须根据题意灵活变化。
• 层间转移的边权、方向和条件需根据题目特性单独分析，避免套模板式误用。

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 1e4 + 5;
int n, m, k, s, t, dis[N * 15], vis[N * 15];
vector<pii> e[N * 15];
void add(int u, int v, int w)
{
    e[u].push_back({v, w});
}
void dijkstra(int s)
{
    for (int i = 1; i <= n * (k + 1); i++)
        dis[i] = 1e9; 
    dis[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({dis[s], s});
    while (q.size())
    {
        auto now = q.top();
        q.pop();
        int u = now.second;
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto it : e[u])
        {
            int v = it.first, w = it.second;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        } 
    } 
} 
int main()
{
    cin >> n >> m >> k >> s >> t;
    s++, t++;
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u++, v++;
        // 层内正常连边
        for (int j = 0; j <= k; j++)
        {
            add(u + j * n, v + j * n, w);
            add(v + j * n, u + j * n, w);
        } 
        // 层与层连边
        for (int j = 0; j < k; j++)
        {
            add(u + j * n, v + (j + 1) * n, 0);
            add(v + j * n, u + (j + 1) * n, 0); 
        } 
    } 
    dijkstra(s);
    int ans = 1e9;
    for (int i = 0; i <= k; i++) ans = min(ans, dis[t + i * n]);
    cout << ans; 
    return 0;
}

---

例题：CF1725M - Moving Both Hands

题意： 给定 $n$ 个点 $m$ 条边的有向图，每条边有边权 $w$。有两个人，一个人站在 $1$ 号点，另一个人站在 $i$ 号点。其中 $i\in [2,n]$。两个人交替移动，问移动到同一个点的最小总移动距离是多少？

问题等价于找到一个点 $x$，使得 $dis(1\to x)+dis(i\to x)$ 最小。

在反图中 $dis(i\to x)$ 和 $dis(x\to i)$ 等价。

考虑建立分层图来完成这个模型，一共两层。

• 第一层：原图 $G$。
• 第二层：反图 $G'$。

第一层如何连向第二层？

第一层的 $i$ 向第二层的 $i+n$ 连一条边，权值为 $0$

这样的话原问题就好比 $dis(1\to x)+dis(x\to x')+dis(x'\to i')$。

• 其中 $x'=x+n,i'=i+n$。

---

例题：[ABC132E] Hopscotch Addict

题意： 给定一张 $n$ 个点 $m$ 条边的有向图，及起点 $s$ 与终点 $t$。从 $s$ 出发，每次可以走恰好 $3$ 步，问要走多少次 $3$ 步，才能到达 $t$。如果不能到达，输出 $-1$。没有重边自环。

$1\le n,m\le 10^5,s\ne t$。

分层图模型

建立三层分层图。

• 第一层：移动步数模 $3$ 为 $0$。
• 第二层：移动步数模 $3$ 为 $1$。
• 第三层：移动步数模 $3$ 为 $2$。

对于原图一条边 $u\to v$，建立 $u\to v+n,u+n\to v+2n,u+2n\to v$ 这样的三条边。

当然也可以拆点做，定义 $dis_{i,j}$ 为走到 $i$，步数模 $3$ 为 $j$ 的最短路，答案则为 $dis_{t,0}$。本质和分层图一样。

---

例题：[ABC192E] Train

题意： 给定一张无向图，每条边 $(u,v)$ 附带两个参数：

• $t$：表示走这条边的时间
• $k$：表示从 $u$ 出发时间必须是 $k$ 的倍数才可以通过

求从起点 $s$ 到终点 $t$ 的最短路径所需时间。

做法：

在每次处理 Dijkstra 的松弛操作时，分类如下：

• 若当前时间 $d$（即 $dis[u]$） 满足 $d \bmod k = 0$，可立刻通行，耗时为 $t$
• 否则需等待 $x = k - (d \bmod k)$ 的时间，总代价为 $t + x$

注意 long long。

long long d = dis[u];
if (d % k == 0) 
{
    if (dis[v] > d + t) 
    {
        dis[v] = d + t;
        q.push({dis[v], v});
    }
} 
else 
{
    long long wait = k - d % k;
    if (dis[v] > d + wait + t) 
    {
        dis[v] = d + wait + t;
        q.push({dis[v], v});
    }
}

---

例题：[CSP-J 2023] 旅游巴士

题意： 有向图中，每条边设有一个限制值 $a$，表示通行前的最早时间要求。

• 起点出发和终点到达的时间必须为 $k$ 的倍数
• 每条边通行时间为 $1$

求从 $1$ 到 $n$ 的最短路，满足所有限制条件。

思路：

拆点即可，设 $dis_{i,j}$ 表示走到点 $i$，当前累计时间模 $k$ 为 $j$ 时的最短距离。

最终答案：$dis_{n,0}$（需满足终点时间为 $k$ 的倍数）

状态转移：分类处理每条边 $u \rightarrow v$（通行限制 $a$）

设当前到达 $u$ 的时间为 $d$：

• 若 $d \geq a$，可直接通行：

\[ dis_{v, (d+1)\bmod k} = \min(dis_{v, (d+1)\bmod k}, dis_{u,d\bmod k} + 1) \]

• 若 $d < a$，必须等待，且等待时间需为 $k$ 的整数倍：
  • 设在起点等待了 $x$ 个 $k$ 的单位时间。则满足：

\[ d+x\cdot k\geq a \]

解得 $x\geq \frac{a-d}{k}$。由于 $x$ 为整数，因此 $x=\lceil\dfrac{a - d}{k}\rceil$。

因此总耗时为 $d+x\cdot k+1$。

void dijkstra(int st)
{
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < k; j++) 
            dis[i][j] = 1e9;
    dis[st][0] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q; // pii = pair<int, int>
    q.push({0, st});
    while (q.size())
    {
        auto it = q.top();
        q.pop();
        int u = it.second, d = it.first;
        if (vis[u][d % k]) continue;
        vis[u][d % k] = 1;
        for (auto it : e[u])
        {
            int v = it.first, a = it.second;
            if (d >= a) // 若 d >= a 可以直接通行
            {
                if (dis[v][(d + 1) % k] > dis[u][d % k] + 1)
                {
                    dis[v][(d + 1) % k] = dis[u][d % k] + 1;
                    q.push({dis[v][(d + 1) % k], v});
                }
            }
            else
            {
                int x = (a - d + k - 1) / k; // 求出至少等待多少倍的 k
                if (dis[v][(d + 1) % k] > d + k * x + 1)
                {
                    dis[v][(d + 1) % k] = d + k * x + 1;
                    q.push({dis[v][(d + 1) % k], v});
                }
            }
        }
    }
}

---

Floyd 相关应用

Floyd 算法除了用于求解多源最短路径外，还有两个重要应用方向：

• 传递闭包：判断任意两点间是否连通
• 最小环问题：在正权无向图中，寻找最小环的权值和

---

传递闭包

问题定义 给定一张有向图（邻接矩阵表示），求其传递闭包，即判断图中任意两点是否 可达。

思想： 将每条边看作 $0/1$ 值，使用 Floyd 思路更新 是否可达。原 Floyd 的 $\texttt{min}$ 被替换为 $\texttt{or}$ 运算。

• 设 $f_{k,i,j}$ 表示仅允许通过编号不超过 $k$ 的中间点时，点 $i$ 是否可以到达点 $j$。

\[ f_{k,i,j} = f_{k-1,i,j} \;||\; (f_{k-1,i,k} \;\&\&\; f_{k-1,k,j}) \]

去除第一维后，我们可以直接进行原地更新：

\[ f_{i,j} = f_{i,j} \;||\; (f_{i,k} \;\&\&\; f_{k,j}) \]

代码实现

时间复杂度：$O(n^3)$。

• $f[i][j] = 1$ 表示 $i$ 能到 $j$，初始值为邻接矩阵。

for (int k = 1; k <= n; k++) 
{
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= n; j++) 
        {
            f[i][j] = f[i][j] || (f[i][k] && f[k][j]);
        }
    }
}

---

bitset 优化传递闭包

若图中点数 $n \leq 2000$，使用布尔数组实现会超时。可使用 $\texttt{bitset}$ 提升效率。

优化关键：将内层循环转为按位与运算。

时间复杂度由 $O(n^3)$ 降为 $O\left( \dfrac{n^3}{w} \right)$，其中 $w$ 为机器字长（通常为 $32$ 或 $64$）。

bitset<N> f[N];

for (int k = 1; k <= n; k++) 
{
    for (int i = 1; i <= n; i++) 
    {
        if (f[i][k]) 
        {
            f[i] |= f[k];  // 相当于 f[i][j] |= f[i][k] & f[k][j]
        }
    }
}

---

无向图的最小环

给定一张正权无向图，求一个 环，使其总权值最小。环需满足：

• 至少包含三个不同的点
• 每条边存在于输入图中

该问题可以通过 Floyd 算法 顺便 求解，在更新最短路的同时记录可能构成环的最小值。

算法思想

Floyd 的特性：三重循环枚举中转点 $k$ 时，意味着路径中不会包含编号大于 $k$ 的点。

在处理第 $k$ 轮中，以 $k$ 为 环的最高点（环上编号最大的点），尝试寻找形如：

\[ i \to j \to k \to i \]

的环，其中 $i < k$, $j < k$。环权值为 $dis_{i,j} + w(i,k) + w(k,j)$。保留最小值即为最小环。

代码实现

int ans = 1e9;
for (int k = 1; k <= n; k++)
{
    // 枚举构成环的两个点 i, j
    for (int i = 1; i < k; i++)
    {
        for (int j = i + 1; j < k; j++)
        {
            if (dis[i][j] < 1e9 && w[i][k] < 1e9 && w[k][j] < 1e9)
                ans = min(ans, dis[i][j] + w[i][k] + w[k][j]);
        }
    }
    // Floyd 更新最短路径
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        }
    }
}

• 初始邻接矩阵：$dis[i][j] = w[i][j]$，无边设为 $\infty$

• 在更新 $dis[i][j]$ 前统计环，否则可能统计到重复或非简单环

---

其余例题：[ABC208D] Shortest Path Queries 2

给定一张 $n$ 个点 $m$ 条边的有向图，定义：

\[ f(s,t,k) = \text{从点 }\ s \text{ 到点 }\ t \text{，只经过点 }\ 1\sim k\ \text{（以及 }\ s,t）\text{ 的最短路径长度} \]

若路径不存在，则 $f(s,t,k) = 0$。要求计算如下总和：

\[ \sum_{k=1}^n \sum_{s=1}^n \sum_{t=1}^n f(s,t,k) \]

其中 $n\leq 400$。

思路： 本题主要考察 Floyd 的本质，而不是背会 Floyd 的代码。

注意到 $f(s,t,k)$ 的定义其实就是 Floyd 的状态设计。因此所求内容即为 Floyd DP 转移过程中，任意两点的路径长度之和。

注意 实现时判断两点路径是否存在。

---

例题：灾后重建

有 $N$ 个村庄（编号 $0$ 到 $N-1$）和 $M$ 条双向道路，每个村庄在地震后将在 $t_i$ 天重建完成，第 $t_i$ 天即可通车。

给出 $Q$ 个询问 $(x, y, t)$，问在第 $t$ 天，从村庄 $x$ 到村庄 $y$ 的最短路径是多少？

注意： 路径必须只经过重建完成时间 $\le t$ 的村庄，否则不能通行。

思路：

Floyd 的核心思想：$dis_{i,j}$ 表示只经过 $1\sim k$ 的点的最短路。

本题中，时间 $t$ 限制了「能使用的中转点」——仅限于 $t_i \le t$ 的村庄。

所以我们可以按村庄重建时间顺序，每次把新恢复的村庄 $k$ 加入 Floyd 外层循环。

查询按时间递增给出，可以边处理边做 Floyd 更新。

状态维护 + 动态更新 Floyd

• 使用 $vis[i]$ 标记村庄 $i$ 是否已恢复。
• 设 $st$ 为上次更新到的编号，$ed$ 为当前时间 $t$ 能用的最大编号。
• 对 $k = st \sim ed$ 执行一轮 Floyd 更新，完成增量更新。

// 当前询问时间为 t，维护恢复村庄
while (i + 1 <= n && a[i + 1] <= t)
    vis[++i] = true;

ed = i;
// Floyd 增量更新
for (int k = st; k <= ed; ++k)
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

处理询问

// 处理本次询问
if (vis[x] && vis[y])
    cout << (dis[x][y] < 1e9 ? dis[x][y] : -1) << "\n";
else
    cout << "-1\n";

st = ed + 1; // 更新下次起点

复杂度分析

• Floyd 每个恢复村庄只处理一次，总复杂度 $O(n^3)$。
• 查询处理为 $O(q)$，查询时间递增使得 Floyd 可增量更新。

• 总复杂度为：$\boxed{O(n^3 + q)}$，在 $n \le 200,\ q \le 5\times 10^4$ 范围内可接受。

• Floyd 外层循环的编号代表 允许作为中转的点，这个语义非常重要。