RE on test#152
题面：
大样例链接
My Code:
#include <bits/stdc++.h>
#define int unsigned long long
#define back_push push_back
using namespace std;
struct Node{
int v,w;
};
struct Node2{
int p,d;
bool operator < (const Node2 & a)const{return a.d>d;}
bool operator > (const Node2 & a)const{return a.d<d;}
};
int n,m,k,s,e;
int pw[55];
int siz;
vector<Node>mp[3200005];
int dis[3200005];
bool vis[3200005];
void dij(){
memset(dis,0x3f,sizeof dis);
priority_queue<Node2,vector<Node2>,greater<Node2> >q;
q.push({s,0});
dis[s] = 0;
while(!q.empty()){
Node2 temp = q.top();
q.pop();
int x = temp.p,d = temp.d;
if(vis[x])continue;
vis[x]=1;
for(int i = 0;i<mp[x].size();i++){
int tt = mp[x][i].v,ww=mp[x][i].w;
if(dis[tt]>dis[x]+ww){
dis[tt]=dis[x]+ww;
if(!vis[tt]){
q.push({tt,dis[tt]});
}
}
}
}
}
signed main(){
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
cin.sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>k;
pw[0] = 1;
siz = 1;
for(int i = 1;i<=32;i++){
if(pw[i-1]*k>1e18){
break;
}
siz++;
pw[i] = pw[i-1]*k;
}
for(int i = 1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
if(k==1){
mp[u].back_push({v,1});
mp[v].back_push({u,1});
continue;
}
for(int j = 1;j<=siz;j++){
//处理第j层
mp[u+n*j-n].back_push({v+n*j-n,w});
mp[v+n*j-n].back_push({u+n*j-n,w});
}
for(int l = 1;l<siz;l++){
//处理第l层到第l+1层的道路
if(pw[l-1]<w){//剪枝
mp[u+n*l-n].back_push({v+n*l,pw[l-1]});//从第1层到第2层要1时间，从第2层到3层要k时间……
mp[v+n*l-n].back_push({u+n*l,pw[l-1]});
}
}
}
cin>>s>>e;
dij();
int mn = LLONG_MAX;
for(int i = 1;i<=siz;i++){
mn = min(mn,dis[i*n-n+e]);
}
cout<<mn;
return 0;
}
