这是第一次做OI题目，问了claude code不少东西，总结了一下：
## 题目概述
– **来源**: 洛谷 P1119，难度 普及+/提高
– **题意**: N 个村庄 (0..N-1)，M 条双向公路。第 i 个村庄在第 t[i] 天修复完成。只有两端村庄均已修复的公路才能使用。Q 次询问 (x, y, T)：第 T 天从 x 到 y 的最短路长度。若起终点未修复或无路径，输出 -1。
– **关键约束**: N ≤ 200, Q ≤ 50000, t[i] 单调不减, 询问时间 T 单调不减, 边权 w ≤ 10000
## 算法分析
### 为什么是 Floyd
N ≤ 200 允许 O(N³) 预处理。Floyd-Warshall 外层循环”for k in 0..N-1″的语义是：以 k 为中间顶点，松弛所有 (i,j) 对。等价于逐步扩大”允许使用的中间顶点集合” S = {0, 1, …, k-1}。
本题中 S 的扩大不由编号顺序驱动，而由修复时间驱动：
– 询问时间 T 单调不减
– t[i] 也单调不减
– 每当 T 推进，解锁所有 t[i] ≤ T 的村庄，用它们作为中间顶点跑一层 Floyd
### DP 状态定义
f(k, i, j) = 从 i 到 j 的最短路径，且路径上所有中间顶点 ∈ {0, 1, …, k-1}
递推式: f(k+1, i, j) = min(f(k, i, j), f(k, i, k) + f(k, k, j))
空间优化（原地覆盖）的可行性：因为 f(k, i, k) = f(k+1, i, k)（k 是终点时，新增 k 作为中间顶点不影响以 k 为端点的路径），所以第 k 轮更新时 dist[i][k] 和 dist[k][j] 是稳定的，可以安全覆盖。
### 复杂度
O(N³ + Q)，N=200 时约 8×10⁶ 次松弛操作。
## 中间顶点顺序无关性的证明
**定理**：逐个添加中间顶点的顺序不影响 Floyd-Warshall 的最终结果。
**分析学视角**：设 P_k = {所有中间顶点来自 {v₀, v₁, …, v_{k-1}} 的路径}。Floyd 维护的量是：
$$d_k(i,j) = \inf\{\text{length}(P) \mid P \in \mathcal{P}_k, P \text{ 从 } i \text{ 到 } j\}$$
关键观察：
1. **单调性**：P_k ⊆ P_{k+1}，于是 d_{k+1} ≤ d_k（infimum over expanding set 单调不增），且有下界（路径长度非负），序列收敛。
2. **最终穷尽**：当 k = n 时，P_n = P（全体路径），d_n = 全局最短路径。
**顺序无关的核心**：infimum over a set 只依赖于最终的集合是什么，不依赖于用怎样的嵌套子集序列去逼近它。无论走 {a}→{a,b}→{a,b,c} 还是 {c}→{b,c}→{a,b,c}，到达全集的瞬间，考虑的候选路径集合完全相同，infimum 自然相同。
**松弛算子的合流性**：每步松弛 $$T_k(d)(i,j) $$= $$min(d(i,j), d(i,k)+d(k,j)) $$是单调算子。施加顺序不同的算子序列对应不同的中间状态，但最终收敛到同一个不动点（Kleene 闭包 / tropical semiring 下的传递闭包）。这类似于重写系统中的 Church-Rosser（合流）性质。
**P1119 推论**：村庄激活顺序按修复时间而非编号，但由上述定理，最终 D[V] 正确。每个查询要求 D[{已修复村庄}][x][y]，恰好是算法在查询时维护的 dist[x][y]。
## AC 代码
“`cpp
/**
* P1119 灾后重建 — 增量 Floyd-Warshall
* =====================================
* 核心思想：Floyd 外层循环的语义是”逐步扩大允许使用的中间顶点集合”。
* 本题中集合扩大不由编号顺序驱动，而由修复时间驱动——
* 询问时间和修复时间均单调不减，两个指针同步向前，
* 每个村庄恰好被作为中间顶点处理一次。
*
* 复杂度：O(N³ + Q)，N=200 时约 8×10⁶ 次松弛，稳过。
*/
#include
using namespace std;
const int INF = 0x3f3f3f3f; // 两倍不溢出 int
const int MAXN = 205; // N ≤ 200
int G[MAXN][MAXN]; // 距离矩阵
int N, M, Q;
// 以顶点 k 为中间点，跑一层 Floyd 松弛
void floyd(int k) {
for (int i = 0; i < N; i++) {
if (G[i][k] == INF) continue;
for (int j = 0; j < N; j++) {
if (G[k][j] == INF) continue;
if (G[i][k] + G[k][j] < G[i][j]) {
G[i][j] = G[i][k] + G[k][j];
}
}
}
}
int main() {
cin >> N >> M;
int t[MAXN];
for (int i = 0; i < N; i++) cin >> t[i];
// 初始化距离矩阵：全 INF，对角 0
memset(G, 0x3f, sizeof(G));
for (int i = 0; i < N; i++) G[i][i] = 0;
// 读入双向边
int u, v, w;
for (int i = 0; i < M; i++) {
cin >> u >> v >> w;
G[u][v] = w;
G[v][u] = w;
}
cin >> Q;
int now = 0; // 下一个待解锁的村庄编号
int x, y, T;
while (Q–) {
cin >> x >> y >> T;
// 解锁所有修复时间 ≤ T 的村庄，逐个跑一层 Floyd
while (now < N && t[now] <= T) {
floyd(now);
now++;
}
// 回答询问
if (t[x] > T || t[y] > T)
cout << -1 << '\n';
else if (G[x][y] == INF)
cout << -1 << '\n';
else
cout << G[x][y] << '\n';
}
return 0;
}
```
## OI 经验总结（首次做题）
### 暴露的问题
- 变量命名冲突：局部变量 `t` 覆盖了数组 `t[MAXN]`，导致 `t[now]` 编译报错
- 运算符混淆：`cout >>` 写成 `<<`（`>>` 是 cin 的）
– 逻辑结构：查询输出放在循环外，导致只输出最后一次结果
– 算法积累不足：虽然理解了 Floyd 的 DP 本质，但第一次见到增量变体需要引导
### 收获
– Floyd-Warshall 外层循环 = 逐个激活中间顶点 = expanding set 上的 infimum
– OI 中 `memset(…, 0x3f, …)` 初始化 INF 的技巧及原理
– `0x3f3f3f3f` 的选择：加法不溢出，memset 一步到位
– OI 赛制特点：允许多次提交但看不到评测数据，需自己造边界数据测试
– 变量名不要和类型名/函数名/已声明数组冲突
### 适用场景
– 动态加点 + 全源最短路查询
– 顶点按某种单调顺序逐步可用
– N 较小 (≤ 500)，允许 O(N³) 预处理