HDU 2026 春季联赛 7 1001 - Card(裴蜀定理) · znzryb
> 杭电 2026 春季联赛 7 第 1 题(HDU 1001)。原题:[https://acm.hdu.edu.cn/contest/problem?cid=1203&pid=1001](https://acm.hdu.edu.cn/contest/problem?cid=1203&pid=1001)
# 题目大意
无向连通图 $n$ 点 $m$ 边,每条边有正权 $w$ 表示走这条边耗费的时间。每个点 $i$ 上有一瓶魔力药水 $a_i$ ,喝一瓶可以让魔力值 $\pm a_i$ (任意次、不耗时间)。从 $1$ 号点出发、初始魔力 $0$ ,目标让魔力值**恰好等于** $V$ ,求最少总移动时间;不可达输出 `-1` 。
约束 $1 \le n, m \le 10^4$ , $1 \le V, a_i, w \le 10^9$ 。题面保证 $a_1$ 的所有质因数都在 $V$ 的质因数集合中(注意这**不蕴含** $a_1 \mid V$ )。
## 样例
```javascript
1
3 2 18
2 3 4
1 2 10
2 3 20
```
输出 `0` 。 $V = 18 = 9 \cdot a_1$ ,起点直接喝 9 次正向药水就行,不用动。
# 思路讲解
## 一句话
> 走过的点的 $a_i$ 通过裴蜀定理可以拼出 $\gcd$ 的所有倍数;问题等价于**找一条从** $1$ **出发的路径,让经过点的** $\gcd$ **整除** $V$ **,最小化总边权**。 $\gcd$ 状态只有 $O(\log V)$ 种,分层图 Dijkstra 直接跑。
## 裴蜀定理转化
走过点集 $S$ 时,每个点 $i \in S$ 都可以喝若干次正向 / 反向药水。最终魔力值是
$\sum_{i \in S} k_i \cdot a_i, \quad k_i \in \mathbb{Z}.$
也就是**关于** $\{a_i\}_{i \in S}$ **的整数线性组合**。
> 🧮 **Note**: **裴蜀定理(Bézout)**: $\{a_i\}$ 的整数线性组合恰好覆盖 $\gcd(a_i : i \in S)$ 的全部整数倍。
所以走过点集 $S$ 的可达魔力值集合 $=$ $\gcd(a_i : i \in S)$ 的全体整数倍。**目标** $V$ **可达** 等价于 $\gcd(S) \mid V$ 。
殊途同归一句:经过一个点不强制喝它的药水,但跳过 $=$ 把它从计入 gcd 的集合里去掉,gcd 只会**变大**、整除关系只会更难满足。所以**最优策略就是把走过的点全喝**,状态干脆只追"目前路径上点的 gcd"一个量。
## gcd 的状态数 $=$ $O(\log V)$
- 起点 gcd $= a_1$
- 每加入一个新点 $v$ , gcd 变成 $\gcd(g, a_v)$ :要么不变( $a_v$ 是 $g$ 的倍数),要么**至少缩小一半**(变成 $g$ 的真因子)
从 $a_1$ 一路降到 $1$ 最多 $\log_2 a_1 = O(\log V)$ 步。出现过的 gcd 全是 $a_1$ 的因数,**每个节点最多** $O(\log V)$ **种 gcd 状态**。
> 关键不变量:状态空间上界 $n \cdot O(\log V) \approx 10^4 \cdot 30 = 3 \times 10^5$ ,分层图 Dijkstra 完全跑得动。
## 分层图 Dijkstra
**状态** $(u, g)$ :当前在节点 $u$ 、当前路径上点的 gcd 是 $g$ 。
**转移**:从 $(u, g)$ 沿边 $(u, v, w)$ 到 $(v, \gcd(g, a_v))$ , dist 加 $w$ 。
**起点** $(1, a_1)$ , dist $= 0$ 。
**答案**:扫所有可达状态 $(u, g)$ ,其中满足 $V \bmod g = 0$ 的最小 dist 即为答案。
边权全正、状态空间有限,标准 Dijkstra(pq + lazy stale check)就够。
## 实现要点
- 用 `vector<map<ll, ll>> mp(n+2)` 存每个节点的 `gcd → dist`
- pq pop 出来 **必须** 先判 `step > mp[u][gcd]` 跳过 stale 态——否则同一个状态反复被 push 出来展开邻居,状态量爆炸 TLE
- 起点先特判 `V % a_1 == 0` 直接输出 `0`
- 找到 ans 后加剪枝 `step + w >= ans` continue
- ans 永远是 `LLONG_MAX` 时输出 `-1` ——题面保证 $a_1$ 的质因数 $\subseteq V$ 的质因数,但**不**蕴含 $a_1 \mid V$ ,反例 $a_1 = 4, V = 18$ 下若所有 $a_i \in \{4, 8, 12, \dots\}$ 永远凑不出 $18$ ,必须返回 `-1`
# AC 代码
[**AC 提交链接**](https://acm.hdu.edu.cn/contest/view-code?cid=1203&rid=10964)
::: 展开完整 C\+\+ 源码
```cpp
// teamname: Gospel_rock
/**
* Problem: Card
* Contest: 2026 杭电春季联赛 7
* Judge: HDOJ
* URL: https://acm.hdu.edu.cn/contest/problem?cid=1203&pid=1001
* Created: 2026-05-08 22:53:45
* Author: Gospel_rock
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct UStepGcd {
ll u, gcd, step;
bool operator<(const UStepGcd &o) const { return step > o.step; }
};
void Solve() {
ll N, M, V;
cin >> N >> M >> V;
vector<ll> A(N + 2);
vector<vector<array<ll, 2>>> g(N + 2);
for (int i = 1; i <= N; ++i) cin >> A[i];
for (int i = 1; i <= M; ++i) {
ll u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
if (V % A[1] == 0) { cout << 0 << "\n"; return; }
priority_queue<UStepGcd> pq;
pq.push({1, A[1], 0});
vector<map<ll, ll>> mp(N + 2);
ll ans = LLONG_MAX;
while (!pq.empty()) {
auto [u, gcd, step] = pq.top();
pq.pop();
if (step > mp[u][gcd]) continue;
for (auto [v, w] : g[u]) {
ll to_gcd = __gcd(A[v], gcd);
if (V % to_gcd == 0) ans = min(ans, step + w);
if (step + w >= ans) continue;
if (!mp[v].contains(to_gcd) || step + w < mp[v][to_gcd]) {
mp[v][to_gcd] = step + w;
} else {
continue;
}
pq.push({v, to_gcd, step + w});
}
}
if (ans == LLONG_MAX) { cout << -1 << "\n"; return; }
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while (T--) Solve();
return 0;
}
```
:::
# 心路历程(TLE → WA → AC)
## 第一版 TLE
`priority_queue + map<ll, map<ll, ll>>` 直接交,TLE 。原因:
- pop 出来**没做 stale check** ,直接处理邻居 → 同一个 `(u, g)` 状态被反复 push、pop、展开邻居,pq 状态量指数膨胀
- `map<ll, map<ll, ll>>` 嵌套红黑树,每次 `contains` / `operator[]` 都是 O(log²) ,常数惨
修法:
1. pop 之后立刻 `if (step > mp[u][gcd]) continue;`
1. 外层换成 `vector<map<ll, ll>>` (节点下标天然是 vector 索引)
1. 顺手加 `step + w >= ans` 早剪枝
## 第二版 WA
修完 TLE 跑通样例,交上去 WA 。原因:
- `ll ans = LLONG_MAX` ,不可达时**没转 -1** 直接打印了 `9223372036854775807`
- 题面要求不可达输出 `-1`
修法:
```cpp
cout << (ans == LLONG_MAX ? -1 : ans) << "\n";
```
题面"保证 $a_1$ 的质因数 $\subseteq V$ 的质因数"乍看像在保证可达,其实**不**蕴含 $a_1 \mid V$ :例如 $a_1 = 4, V = 18$ , $\{2\} \subseteq \{2, 3\}$ 满足前提,但 $4 \nmid 18$ 。如果整张图所有 $a_i$ 都是 $4$ 的倍数(gcd 永远是 $4$ 的倍数)就永远凑不出 $18$ ,必须返回 `-1` 。
加上这一行后 AC 。
# 附件
(暂无)