: 上学)
2025年3月GESP真题及题解(C++八级): 上学
题目描述
C 城可以视为由n nn个结点与m mm条边组成的无向图。 这些结点依次以1 , 2 , … , n 1, 2, \ldots, n1,2,…,n标号，边依次以1 ≤ i ≤ m 1 \leq i \leq m1≤i≤m连接边号为u i u_iui与v i v_ivi的结点，长度为l i l_ili米。
小 A 的学校坐落在 C 城的编号为s ss的结点。小 A 的同学们共有q qq位，他们想在保证不迟到的前提下，每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校，于是找到了聪明的小 A。第i ii位同学 (1 ≤ i ≤ q 1 \leq i \leq q1≤i≤q) 告诉小 A，他的家位置于编号为h i h_ihi的结点，并且他每秒钟能行走 1 米。请你帮小 A 计算，每位同学从家出发需要多少秒才能到达学校呢？
输入格式
第一行，四个正整数n , m , s , q n, m, s, qn,m,s,q，分别表示 C 城的结点数与边数，学校所在的结点编号，以及小 A 同学们的数量。
接下来m mm行，每行三个正整数u i , v i , l i u_i, v_i, l_iui,vi,li，表示 C 城中的一条无向边。
接下来q qq行，每行一个正整数h i h_ihi，表示一位同学的情况。
输出格式
共q qq行，对于每位同学，输出一个整数，表示从家出发到学校的最短时间。
输入输出样例 1
输入 1
5 5 3 3 1 2 3 2 3 2 3 4 1 4 5 3 1 4 2 5 1 4输出 1
4 3 1说明/提示
对于20 % 20\%20%的测试点，保证q = 1 q = 1q=1。
对于另外20 % 20\%20%的测试点，保证1 ≤ n ≤ 500 1 \leq n \leq 5001≤n≤500，1 ≤ m ≤ 500 1 \leq m \leq 5001≤m≤500。
对于所有测试点，保证1 ≤ n ≤ 2 × 10 5 1 \leq n \leq 2 \times 10^51≤n≤2×105，1 ≤ m ≤ 2 × 10 5 1 \leq m \leq 2 \times 10^51≤m≤2×105，1 ≤ q ≤ 2 × 10 5 1 \leq q \leq 2 \times 10^51≤q≤2×105，1 ≤ u i , v i , s , h i ≤ n 1 \leq u_i, v_i, s, h_i \leq n1≤ui,vi,s,hi≤n，1 ≤ l i ≤ 10 6 1 \leq l_i \leq 10^61≤li≤106。
题目分析
本题要求计算从学校结点s到每个同学家结点h_i的最短路径长度（单位：米）。由于行走速度为1米/秒，所以最短路径长度即为所需时间（秒）。这是一个典型的单源最短路径问题，给定无向图、正权边，需要高效处理最多2e5个结点和边的规模。
算法思路
- 建模：将城市抽象为无向图，结点数
n，边数m，每条边有长度l_i（权值）。 - 最短路径计算：使用Dijkstra 算法（堆优化版本），从源点
s开始计算到所有结点的最短距离。复杂度为 O((n+m) log n)，可以处理2e5的数据规模。 - 查询处理：预处理出所有最短距离后，对每个查询
h_i直接输出dist[h_i]。
注意事项
- 边权最大1e6，边数最多2e5，总距离可能超过
int范围，需使用long long。 - 图可能不连通，但题目未明确说明。为安全起见，初始化距离为极大值（如1e18），不可达时输出该值（但根据题意通常连通）。
代码实现
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintMAXN=200010;// 最大结点数constll INF=1e18;// 表示无穷大的距离intn,m,s,q;// 结点数、边数、学校结点、查询数vector<pair<int,ll>>graph[MAXN];// 邻接表ll dist[MAXN];// 从学校到各点的最短距离// Dijkstra 算法，计算从起点 start 到所有点的最短距离voiddijkstra(intstart){// 初始化所有距离为无穷大for(inti=1;i<=n;++i)dist[i]=INF;dist[start]=0;// 小顶优先队列，存储 (当前距离, 结点编号)priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;pq.push({0,start});while(!pq.empty()){// 取出当前距离最小的结点ll d=pq.top().first;intu=pq.top().second;pq.pop();// 如果这个距离已经大于记录的距离，说明是旧数据，跳过if(d>dist[u])continue;// 遍历所有邻接点for(auto&edge:graph[u]){intv=edge.first;ll w=edge.second;// 如果通过 u 到 v 的距离更短，则更新if(dist[u]+w<dist[v]){dist[v]=dist[u]+w;pq.push({dist[v],v});}}}}intmain(){// 读入基本数据scanf("%d %d %d %d",&n,&m,&s,&q);// 读入边信息，构建无向图for(inti=0;i<m;++i){intu,v;ll l;scanf("%d %d %lld",&u,&v,&l);graph[u].push_back({v,l});graph[v].push_back({u,l});// 无向边，双向添加}// 运行 Dijkstra，计算从学校到所有点的最短距离dijkstra(s);// 处理每个查询，直接输出最短距离（即时间）while(q--){inth;scanf("%d",&h);printf("%lld\n",dist[h]);}return0;}功能分析
- 图构建：使用邻接表存储无向图，每个边记录终点和权值。
- 最短路径计算：
- 初始化距离数组
dist，源点s距离为0。 - 使用优先队列（最小堆）维护当前未确定最短距离的结点，每次取出距离最小的结点进行松弛操作。
- 对每条边进行松弛，若找到更短路径则更新距离并加入队列。
- 初始化距离数组
- 查询响应：由于已预处理所有最短距离，每个查询只需 O(1) 时间输出结果。
- 时间复杂度：Dijkstra 算法 O((n+m) log n)。
- 空间复杂度：O(n+m)，用于存储图和距离数组。
样例验证
输入：
5 5 3 3 1 2 3 2 3 2 3 4 1 4 5 3 1 4 2 5 1 4计算过程：
- 从结点3出发，最短距离：
- dist[3]=0
- dist[2]=2
- dist[4]=1
- dist[1]=min(3→2→1=5, 3→4→1=3)=3
- dist[5]=min(3→4→5=4, 其他路径更长)=4
- 查询输出：
- h=5 → 4
- h=1 → 3
- h=4 → 1
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
