P9026 [CCC 2021 S4] Daily Commute题目描述已知有N NN个地铁站你家在1 11学校在N NN。有W WW条单向人行道。经过需要一分钟。此外还有一条环形地铁线路依次经过S 1 , S 2 , ⋯ , S N S_1,S_2,\cdots,S_NS1​,S2​,⋯,SN​且保证S 1 1 S_11S1​1。每天有且仅有一辆地铁在0 00时刻从S 1 S_1S1​出发并且恰好在第i ii分钟到达S i S_iSi​。在接下来D DD天中交换S X i S_{X_i}SXi​​和S Y i S_{Y_i}SYi​​。注意修改是永久的。查询从1 11到N NN的最短用时。你出发时地铁在1 11。输入格式第一行N , W , D N,W,DN,W,D。接下来W WW行A i , B i A_i,B_iAi​,Bi​表示单向人行道。接下来一行N NN个数S SS。接下来D DD行X i , Y i X_i,Y_iXi​,Yi​保证2 ≤ X i , Y i ≤ N , X i ≠ Y i 2\leq X_i,Y_i\leq N,X_i\neq Y_i2≤Xi​,Yi​≤N,Xi​Yi​。输出格式D DD行每天的答案。输入输出样例 #1输入 #14 3 3 1 2 3 4 4 1 1 4 3 2 3 4 4 2 3 2输出 #11 2 3说明/提示3 ≤ N ≤ 200000 , 0 ≤ W ≤ 200000 , 1 ≤ D ≤ 200000 3\leq N\leq 200000,0\leq W\leq 200000,1\leq D\leq 2000003≤N≤200000,0≤W≤200000,1≤D≤200000译自 CCC2021 S4。请注意常数。C实现#includestdio.h#includequeue#defineN222222#defineprpairint,intusingnamespacestd;inlinecharnc(){staticcharbuf[99999],*l,*r;returnlr(r(lbuf)fread(buf,1,99999,stdin),lr)?EOF:*l;}inlinevoidread(intx){charcnc();for(;c0||9c;cnc());for(x0;0cc9;x(x3)(x1)(c^48),cnc());}inlinevoidpc(constcharc){staticcharbuf[99999],*rbuf;(!c||(*rc,rbuf99999))(fwrite(buf,1,r-buf,stdout),rbuf);}inlinevoidpi(constintx){if(x9)pi(x/10);pc(x%100);}intn,m,d,s[N],a[N],h[N],e[N],nxt[N],dis[N];priority_queuepr,vectorpr,greaterprqwq;dequeintq;main(){read(n);read(m);read(d);for(inti1,u,v;im;i)read(u),read(v),--u,--v,e[i]u,nxt[i]h[v],h[v]i;for(inti0,x;in;read(s[i]),a[--s[i]]i,dis[i]130);q.emplace_back(n-1);dis[n-1]0;for(inti;q.size();){iq.front();q.pop_front();for(intjh[i];j;jnxt[j])if(dis[e[j]]30)dis[e[j]]dis[i]1,q.emplace_back(e[j]);}for(inti0;in;i)qwq.emplace(dis[i]a[i],i);for(intu,v;d--;pi(qwq.top().first),pc(\n)){read(u);read(v);--u;--v;swap(s[u],s[v]);us[u];vs[v];swap(a[u],a[v]);qwq.emplace(dis[u]a[u],u);qwq.emplace(dis[v]a[v],v);for(;qwq.top().first^dis[qwq.top().second]a[qwq.top().second];qwq.pop());}pc(0);}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容