题意
给你一个图，跑最短路，如果经过点 $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;
}