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

· · 题解

题意

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

思路

双倍经验。

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

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,m,l,dis[1000001],mn=0x3f3f3f3f3f3f3f3f;
vector<pair<ll,ll>>g[1000001];
//建边
void add(ll x,ll y,ll z){g[x].push_back({y,z});}
//最短路
void dij(){
    memset(dis,0x3f,sizeof dis);
    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});
    }
}
int main(){
    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;//输出
    else cout<<-1;
    return 0;
}