这是 @方嘉南 的代码，WA on #187(本来还RE on #152，已被我修正)
#include<bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
const int N=2e5+5,FJNAKIOI=1e9;
int n,m,k,S,T;
int cnt=1;
struct edge{
int v,w;
bool operator<(const edge &ano)const{
return ano.w<w;
}
};
vector<edge> g[N*40];
priority_queue<edge> q;
int dis[N*40],ans=0x3f3f3f3f3f3f3f;
bool vis[N*40];
void Dijkstra(){
for(int i=1;i<=n*cnt;i++){
dis[i]=ans;
}
dis[S]=0;
q.push({S,0});
while(!q.empty()){
int u=q.top().v;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto it:g[u]){
int v=it.v,w=it.w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({v,dis[v]});
}
}
}
}
signed main(){
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
cin>>n>>m>>k;
int u,v,w;
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
if(k!=1){
g[u].push_back({v,w});
g[v].push_back({u,w});
}else{
g[u].push_back({v,1});
g[v].push_back({u,1});
}
}
ll t=1;
while(t<=FJNAKIOI){
if(k==1) break;
for(int u=1;u<=n;u++){
for(auto it:g[u]){
int v=it.v;
if(v>n) break;
g[u+(cnt-1)*n].push_back({v+cnt*n,(int)t});
g[u+cnt*n].push_back({v+cnt*n,it.w});
}
}
t*=k;
cnt++;
}
cin>>S>>T;
Dijkstra();
for(int i=0;i<cnt;i++) ans=min(ans,dis[T+n*i]);
cout<<ans<<"\n";
return 0;
}
这个点我拼尽全力无法战胜，根据初步的检查感觉问题在第61行