洛谷题解：P16273 [蓝桥杯 2026 省 Java B 组] 回程

题意

给你一个图，跑最短路，如果经过点x xx，那么就可以三次让经过的一条边的边权变成1 11。

思路

双倍经验。

这题可以用分层图，每条边可以跨层连接两个点，边权是1 11。意思是使用一次特殊机会。
和 P4568 不同的是，这题要经过点x xx才可以有优惠，所以可以多开一层，这一层只有x xx和下一层连接，边权为0 00。意思是只要经过点x xx，才可以有优惠。

代码

#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;ll n,m,l,dis[1000001],mn=0x3f3f3f3f3f3f3f3f;vector<pair<ll,ll>>g[1000001];//建边voidadd(ll x,ll y,ll z){g[x].push_back({y,z});}//最短路voiddij(){memset(dis,0x3f,sizeofdis);priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>q;q.push({dis[n]=0,n});while(!q.empty()){auto[d,x]=q.top();q.pop();if(d>dis[x])continue;for(auto[y,z]:g[x])if(dis[y]>d+z)q.push({dis[y]=d+z,y});}}intmain(){cin>>n>>m>>l,add(l,l+n,0);//经过x才可以优惠for(ll i=1,x,y,z;i<=m;i++){cin>>x>>y>>z;//相同层建边for(ll j=0;j<5;j++)add(x+j*n,y+j*n,z),add(y+j*n,x+j*n,z);//不同层可以有优惠for(ll j=1;j<4;j++)add(x+j*n,y+(j+1)*n,1),add(y+j*n,x+(j+1)*n,1);}dij();//跑最短路for(ll i=0;i<5;i++)//取不同层最小值mn=min(mn,dis[1+i*n]);if(mn!=0x3f3f3f3f3f3f3f3f)cout<<mn;//输出elsecout<<-1;return0;}

原文链接