252.上学

markdown
复制
1# 上学 题解
2
3## 题目分析
4
5本题给出一个由 \(n\) 个结点和 \(m\) 条边组成的无向连通图，每条边有一个长度 \(l_i\)。学校位于结点 \(S\)。有 \(Q\) 位同学，第 \(i\) 位同学的家位于结点 \(h_i\)，且每秒能行走 \(1\) 米。题目要求计算每位同学从家到学校的最短时间。
6
7由于速度恒为 \(1\) 米/秒，因此从 \(h_i\) 到 \(S\) 的最短时间就等于两点之间的最短路径长度。问题转化为**单源最短路径问题**：以 \(S\) 为源点，求出到图中所有结点的最短距离，然后对每个查询直接输出距离即可。
8
9## 解题思路
10
11本题的数据范围为：
12
13- \(1 \le n, m, Q \le 2\times 10^5\)
14- 边权 \(1 \le l_i \le 10^6\)
15
16边权全部为正，且图的规模较大，因此需要使用 **堆优化 Dijkstra 算法**。朴素 Dijkstra 的时间复杂度为 \(O(n^2)\)，在 \(n=2\times 10^5\) 时会超时，而堆优化版本可以将复杂度降至 \(O((n+m)\log n)\)，能够在时限内运行完毕。
17
18具体步骤如下：
19
201. **建图**：使用邻接表存储无向图，每条无向边需要拆成两条有向边，**两条有向边的权值均为原边权**。
212. **初始化**：将源点 \(S\) 的距离设为 \(0\)，其他点的距离设为无穷大（如 \(10^{18}\)）。使用一个优先队列（小根堆）存储 `(距离, 结点)`，并将 \((0, S)\) 入队。
223. **松弛操作**：每次从堆中取出当前距离最小的结点 \(u\)，若 \(u\) 已被访问过则跳过；否则标记已访问，遍历 \(u\) 的所有出边 \((u, v, w)\)，若 \(d[u] + w < d[v]\)，则更新 \(d[v]\) 并将 \((d[v], v)\) 入队。
234. **回答询问**：预处理完毕后，对于每位同学的家 \(h_i\)，直接输出 \(d[h_i]\) 即可。
24
25## 算法说明（Dijkstra + 优先队列）
26
27Dijkstra 算法基于贪心思想：每次选择当前最短距离已知且未访问的结点，对其进行松弛操作。由于图中的边权均为正，这种贪心策略可以保证每个结点被第一次从堆中取出时，其距离即为最终的最短距离。
28
29在实现中使用 `std::priority_queue`，默认是大根堆，因此我们通常插入距离的**相反数**或使用 `greater` 比较器来得到小根堆的效果。参考代码中采用插入 `-d[v]` 的方式实现小根堆。
30
31**关于参考代码的勘误**：
32题目提供的参考代码中，添加反向边时误将权值写成了 `1`：
33
34```cpp
35ae(u, v, l);
36ae(v, u, 1);   // 错误：应为 ae(v, u, l);

这会导致部分路径的计算出现严重偏差，无法通过测试。正确做法是两条有向边的权值都必须是读入的 l。请以题解末尾给出的修正代码为准。

时间复杂度分析

• 建图：每条边添加两条有向边，复杂度 (O(m))。
• Dijkstra 主循环：每个结点最多入堆一次、出堆一次，每条边最多被松弛一次。优先队列的插入和删除操作复杂度为 (O(\log n))，因此总复杂度为 (O((n + m)\log n))。
• 回答询问：(O(Q)) 直接输出。

总时间复杂度为 (O((n + m)\log n + Q))，在 (2\times 10^5) 的规模下可以快速运行。

空间复杂度分析

邻接表存储 (2m) 条有向边，加上距离数组 d 和访问标记数组 vis，空间复杂度为 (O(n + m))，同样满足内存限制 512MB 的要求。

参考代码

以下是修正后的完整 Dijkstra 实现：

cpp
复制
1#include <cstdio>
2#include <queue>
3#include <vector>
4using namespace std;
5
6const int N = 2e5 + 5;
7const int E = N << 1;                // 无向边拆成两条有向边
8const long long INF = 1e18;
9
10int n, m, S, Q;
11int head[N], to[E], nxt[E], wt[E], tot;
12long long dist[N];
13bool vis[N];
14
15// 添加有向边 u -> v，权值为 w
16void add_edge(int u, int v, int w) {
17    tot++;
18    to[tot] = v;
19    wt[tot] = w;
20    nxt[tot] = head[u];
21    head[u] = tot;
22}
23
24int main() {
25    scanf("%d %d %d %d", &n, &m, &S, &Q);
26    for (int i = 1; i <= m; i++) {
27        int u, v, l;
28        scanf("%d %d %d", &u, &v, &l);
29        add_edge(u, v, l);
30        add_edge(v, u, l);            // 修正：反向边权值与正向边相同
31    }
32
33    // 初始化距离
34    for (int i = 1; i <= n; i++)
35        dist[i] = INF;
36    dist[S] = 0;
37
38    // 小根堆：存储 (-距离, 结点)
39    priority_queue<pair<long long, int>> pq;
40    pq.push({0, S});
41
42    while (!pq.empty()) {
43        int u = pq.top().second;
44        pq.pop();
45        if (vis[u]) continue;
46        vis[u] = true;
47        for (int i = head[u]; i; i = nxt[i]) {
48            int v = to[i], w = wt[i];
49            if (dist[u] + w < dist[v]) {
50                dist[v] = dist[u] + w;
51                pq.push({-dist[v], v});   // 取相反数实现小根堆
52            }
53        }
54    }
55
56    // 回答询问
57    while (Q--) {
58        int h;
59        scanf("%d", &h);
60        printf("%lld\n", dist[h]);
61    }
62    return 0;
63}

代码说明

• 邻接表建图：使用 head、to、nxt、wt 数组模拟链表，add_edge 函数每次添加一条有向边。由于是无向图，需要调用两次 add_edge，并传入相同的权值。
• 距离数组：dist[i] 存储从源点 (S) 到结点 (i) 的最短距离，初始为 INF ((10^{18}))，dist[S] = 0。
• 优先队列优化：priority_queue 默认是大根堆，插入 -dist[v] 使得堆顶为当前距离最小的结点。通过 vis 数组避免重复处理。
• 无穷大取值：因为最大路径长度可达 (n \times l_{\max} \approx 2\times 10^5 \times 10^6 = 2\times 10^{11})，使用 1e18 足以覆盖。
• 输入输出：为保证效率使用 scanf/printf。注意距离使用 long long 类型，输出格式为 %lld。

总结

本题是经典的单源最短路模板题，考察对 Dijkstra 算法及其堆优化的掌握。关键点在于：

• 识别出问题本质是求最短路。
• 根据数据范围选择合适的算法（堆优化 Dijkstra）。
• 在代码实现时务必注意细节，例如无向边权值的正确添加，以及使用 long long 防止溢出。

修正上述错误后，即可顺利通过所有测试点。