ICPC 2025区域赛 西安站 F题题解

题目链接：P14452 [ICPC 2025 Xi’an R] Follow the Penguins

建议本题标签：图论，最短路。

这道题要求求解每个企鹅的停止时间，

可以发现本题类似于最短路问题，企鹅停止存在非严格（可能同时停止）的先后顺序，每当有企鹅停止时，使用停止的企鹅去更新其他未停止企鹅的状态即可（只需要更新以当前停止企鹅为目标企鹅的企鹅状态，即认为二者之间存在一条单向边），我们可以使用dijkstra 算法来解决该问题，代码实现较为模板化，本题难度主要在理解题意与图论建模。

算法具体流程：

我们先做一个预处理，定义方向数组w ww，值为 1 表示该企鹅正向走，值为 0 表示该企鹅反向走，根据企鹅当前位置以及目标企鹅位置能完成一开始方向数组的初始化。

初始化所有企鹅的当前停止时间（方向相同则为 INF ），我们对这个当前停止时间进行堆排序，每次在还未停止的企鹅中取出预计停止时间最小的企鹅，把他取出（即时间已经到了该企鹅的停止时间），然后更新所有以他为目标的企鹅的当前停止时间，重复此过程，直到所有企鹅都停止，此时所有企鹅的当前停止时间即为最终答案。

时间复杂度即为 Dijkstra 算法的时间复杂度，在本题解给出的具体实现中是O ( m log ⁡ n ) O(m \log n)O(mlogn)，即优先队列维护的 dijkstra 算法，本题为稀疏图，而且很明显是m = n m = nm=n的。

以下是具体的代码实现：

#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constll INF=(1ll<<60);intmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);intn;cin>>n;vector<int>t(n+1);vector<vector<int>>edges(n+1);for(inti=1;i<=n;i++){cin>>t[i];edges[t[i]].push_back(i);}vector<int>a(n+1);for(inti=1;i<=n;i++){cin>>a[i];a[i]*=2;}vector<char>w(n+1);//不使用特化的vector<bool>//1为正向，0为反向for(inti=1;i<=n;i++)w[i]=(a[i]<=a[t[i]]);vector<ll>nowt(n+1,INF);usingP=pair<ll,int>;priority_queue<P,vector<P>,greater<P>>pq;for(inti=1;i<=n;i++){if((w[i]^w[t[i]])==1)nowt[i]=llabs(a[i]-a[t[i]])/2;//实际上全是偶数，除2依然是整数pq.push({nowt[i],i});}vector<char>done(n+1,0);while(!pq.empty()){auto[tm,x]=pq.top();pq.pop();//已停止or该键过期if(done[x]||tm!=nowt[x])continue;done[x]=1;ll posx=w[x]?a[x]+tm:a[x]-tm;//posx是x停止的位置for(inty:edges[x]){if(done[y])continue;ll posy=w[y]?a[y]+tm:a[y]-tm,nt=tm+llabs(posx-posy);//一只企鹅停止后速度减半，更新nowtnowt[y]=nt;pq.push({nowt[y],y});}}for(inti=1;i<=n;i++)cout<<nowt[i]<<" ";return0;}

ps .代码虽然经过优化，但还可以更为简短精炼，考虑到赛场实际情况，最终采用以上版本。

代码变量解释：

1. 目标企鹅编号（数组t tt）。
2. 以当前企鹅为目标企鹅的企鹅编号（邻接表e d g e s edgesedges）。
3. 每只企鹅的所在位置（数组a aa， *2 以免出现浮点数，此时企鹅速度为每秒 1 个单位长度）。
4. 方向数组w ww（值为 1 表示该企鹅正向走，值为 0 表示该企鹅反向走）。
5. 企鹅当前停止时间（数组n o w t nowtnowt，全部更新完后即为最终答案）。
6. 优先队列p q pqpq，小根堆，以当前停止时间为 value 。
7. 企鹅是否停止（数组d o n e donedone）。