题意给你一个图跑最短路如果经过点x xx那么就可以三次让经过的一条边的边权变成1 11。思路双倍经验。这题可以用分层图每条边可以跨层连接两个点边权是1 11。意思是使用一次特殊机会。和 P4568 不同的是这题要经过点x xx才可以有优惠所以可以多开一层这一层只有x xx和下一层连接边权为0 00。意思是只要经过点x xx才可以有优惠。代码#includebits/stdc.husingnamespacestd;usinglllonglong;ll n,m,l,dis[1000001],mn0x3f3f3f3f3f3f3f3f;vectorpairll,llg[1000001];//建边voidadd(ll x,ll y,ll z){g[x].push_back({y,z});}//最短路voiddij(){memset(dis,0x3f,sizeofdis);priority_queuepairll,ll,vectorpairll,ll,greaterpairll,llq;q.push({dis[n]0,n});while(!q.empty()){auto[d,x]q.top();q.pop();if(ddis[x])continue;for(auto[y,z]:g[x])if(dis[y]dz)q.push({dis[y]dz,y});}}intmain(){cinnml,add(l,ln,0);//经过x才可以优惠for(ll i1,x,y,z;im;i){cinxyz;//相同层建边for(ll j0;j5;j)add(xj*n,yj*n,z),add(yj*n,xj*n,z);//不同层可以有优惠for(ll j1;j4;j)add(xj*n,y(j1)*n,1),add(yj*n,x(j1)*n,1);}dij();//跑最短路for(ll i0;i5;i)//取不同层最小值mnmin(mn,dis[1i*n]);if(mn!0x3f3f3f3f3f3f3f3f)coutmn;//输出elsecout-1;return0;}原文链接