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 nmn的。以下是具体的代码实现#includebits/stdc.husingnamespacestd;usinglllonglong;constll INF(1ll60);intmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);intn;cinn;vectorintt(n1);vectorvectorintedges(n1);for(inti1;in;i){cint[i];edges[t[i]].push_back(i);}vectorinta(n1);for(inti1;in;i){cina[i];a[i]*2;}vectorcharw(n1);//不使用特化的vectorbool//1为正向0为反向for(inti1;in;i)w[i](a[i]a[t[i]]);vectorllnowt(n1,INF);usingPpairll,int;priority_queueP,vectorP,greaterPpq;for(inti1;in;i){if((w[i]^w[t[i]])1)nowt[i]llabs(a[i]-a[t[i]])/2;//实际上全是偶数除2依然是整数pq.push({nowt[i],i});}vectorchardone(n1,0);while(!pq.empty()){auto[tm,x]pq.top();pq.pop();//已停止or该键过期if(done[x]||tm!nowt[x])continue;done[x]1;ll posxw[x]?a[x]tm:a[x]-tm;//posx是x停止的位置for(inty:edges[x]){if(done[y])continue;ll posyw[y]?a[y]tm:a[y]-tm,nttmllabs(posx-posy);//一只企鹅停止后速度减半更新nowtnowt[y]nt;pq.push({nowt[y],y});}}for(inti1;in;i)coutnowt[i] ;return0;}ps .代码虽然经过优化但还可以更为简短精炼考虑到赛场实际情况最终采用以上版本。代码变量解释目标企鹅编号数组t tt。以当前企鹅为目标企鹅的企鹅编号邻接表e d g e s edgesedges。每只企鹅的所在位置数组a aa *2 以免出现浮点数此时企鹅速度为每秒 1 个单位长度。方向数组w ww值为 1 表示该企鹅正向走值为 0 表示该企鹅反向走。企鹅当前停止时间数组n o w t nowtnowt全部更新完后即为最终答案。优先队列p q pqpq小根堆以当前停止时间为 value 。企鹅是否停止数组d o n e donedone。