题目题解

问题理解

给定一个简单无向连通图，从顶点 $1$ 出发，每个顶点 $u$ 的边按输入顺序编号为 $1$ 到 $\deg(u)$。在时间 $t$，若位于顶点 $u$，必须执行以下操作之一：

• 等待一秒，
• 通过顶点 $u$ 的第 $(t \bmod \deg(u) + 1)$ 条边移动到邻接点，耗时一秒。

求从顶点 $1$ 到顶点 $n$ 的最短总时间，以及在此最短总时间下的最少等待时间。

---

状态定义

设 $f(i, j)$ 表示在时间 $j$ 到达顶点 $i$ 所需的最少等待时间。初始状态为

$$f(1, 0) = 0.$$

---

状态转移

在时间 $j$ 位于顶点 $i$，有以下两种转移：

1. 等待一秒：
   时间变为 $j+1$，等待时间增加 $1$：

   $$f(i, j+1) \leftarrow \min\big(f(i, j+1),\; f(i, j) + 1\big). $$

2. 移动：
   设 $k$ 为顶点 $i$ 的第 $(j \bmod \deg(i) + 1)$ 条边所连的顶点。则移动后时间变为 $j+1$，等待时间不变：

   $$f(k, j+1) \leftarrow \min\big(f(k, j+1),\; f(i, j)\big). $$

---

目标

设 $x$ 为从 $1$ 到 $n$ 的最短总时间，则最小等待时间为

$$f(n, x).$$

因此，只需对所有 $j \le x$ 计算 $f(i, j)$。

---

时间复杂度分析

若直接计算到时间 $x$，复杂度为 $O(n x + m)$。
我们需要给出 $x$ 的上界。

---

上界 $x \le 3n$

引理：存在一条从 $1$ 到 $n$ 的路径，其顶点度数之和 $d \le 3n$。

证明：

• 取一条从 $1$ 到 $n$ 的最短路径（边数最少），设路径上有 $k$ 个顶点。
• 由于路径是最短的，不存在连接路径上非相邻顶点的边（否则可缩短路径）。
• 也不存在路径外的一个顶点与路径上至少 $4$ 个顶点相邻，因为那样同样可以缩短路径。

因此，路径上每个顶点的度数最多为 $2$（与路径上前后顶点相邻）加上可能的路径外邻接点。
由于每个路径外顶点最多与 $3$ 个路径上顶点相邻，所以路径上顶点的度数之和满足：

$$\sum_{u \in \text{path}} \deg(u) \le 2k + 3(n - k) = 3n - k. $$

由于 $k \ge 2$，有

$$\sum_{u \in \text{path}} \deg(u) \le 3n.$$

---

最坏情况下的总时间

考虑这条路径，最坏策略是每次前进前等待到该顶点对应边出现。
对于路径上的顶点 $u$，最多等待 $\deg(u) - 1$ 次（因为总有一时刻当前边就是要用的边）。
因此，总时间不超过路径上所有顶点的度数之和，即 $x \le 3n$。

---

算法复杂度

由于 $x \le 3n$，我们可以计算所有 $j \le 3n$ 的状态。
状态数 $O(n \cdot 3n) = O(n^2)$，每个状态转移 $O(1)$，加上边信息预处理 $O(m)$，总复杂度为

$$O(n^2 + m).$$

对于 $n \le 5000$ 且 $\sum n \le 5000$，这是可行的。

---

算法步骤

1. 读入图，计算每个顶点的度数及边的顺序。
2. 初始化 $f(1,0) = 0$，其余 $f(i,j) = \infty$。
3. 对 $j = 0$ 到 $3n-1$：
   • 对于每个顶点 $i$，若 $f(i,j)$ 已知：
     • 更新 $f(i, j+1) = \min(f(i, j+1), f(i,j) + 1)$
     • 设 $k$ 为 $i$ 的第 $(j \bmod \deg(i) + 1)$ 条边的另一端点，更新 $f(k, j+1) = \min(f(k, j+1), f(i,j))$
4. 找到最小的 $x$ 使得 $f(n, x)$ 有限，输出 $x$ 和 $f(n, x)$。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

void solve() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> g(n);
    vector<int> deg(n, 0);
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    
    int max_time = 3 * n;  // 上界
    
    // f[i][j] = 在时间 j 到达顶点 i 的最少等待时间
    vector<vector<int>> f(n, vector<int>(max_time + 1, INF));
    f[0][0] = 0;
    
    for (int j = 0; j < max_time; j++) {
        for (int i = 0; i < n; i++) {
            if (f[i][j] == INF) continue;
            
            // 等待操作
            f[i][j + 1] = min(f[i][j + 1], f[i][j] + 1);
            
            // 移动操作
            int edge_idx = j % deg[i];
            int to = g[i][edge_idx];
            f[to][j + 1] = min(f[to][j + 1], f[i][j]);
        }
    }
    
    // 寻找答案
    int best_time = INF, best_wait = INF;
    for (int j = 0; j <= max_time; j++) {
        if (f[n - 1][j] < best_time) {
            best_time = j;
            best_wait = f[n - 1][j];
        } else if (f[n - 1][j] == best_time) {
            best_wait = min(best_wait, f[n - 1][j]);
        }
    }
    
    cout << best_time << " " << best_wait << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

---

验证样例

样例 1：输出 4 2 ✓
样例 2：输出 3 0 ✓

---

总结

本题的关键在于：

1. 将问题转化为带时间维度的状态搜索。
2. 利用最短路径的性质给出时间上界 $3n$，从而将复杂度控制在 $O(n^2 + m)$。
3. 通过动态规划或 BFS 在有限时间范围内求解，并同时记录最少等待时间。