rt,不知道为什么重载运算符寄了,不知道哪里的问题
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e4+10,M=110,inf=0x3f3f3f3f;
int n,m,k;
int dist[N][M];
bool st[N][M];
//dist(i,j),st(i,j)到达i点,此时走的路程%k=j
//因为我们从起点出发后,只要求起点与终点的时间差是k的倍数
int h[N],e[N],ne[N],idx,TT[N];
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],TT[idx]=c,h[a]=idx++;
}
struct Nd{
int u,i,nw_t;
bool operator<(const Nd &f)const{
return nw_t<f.nw_t;
}
};
signed main(){
memset(h,-1,sizeof(h));
scanf("%lld%lld%lld",&n,&m,&k);
int u,v,w;
while(m--){
scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w);
}
priority_queue<Nd,vector<Nd>,greater<Nd> > q;
memset(dist,0x3f,sizeof(dist));
q.push({1,0,dist[1][0]=0});
while(!q.empty()){
Nd t=q.top();q.pop();
int ver=t.u,tim=t.nw_t;
for(int i=h[ver];~i;i=ne[i]){
int j=e[i];
if(TT[i]>t.nw_t) t.nw_t+=(TT[i]-t.nw_t+k-1)/k*k;
if(dist[j][(t.i+1)%k]>t.nw_t+1){
dist[j][(t.i+1)%k]=t.nw_t+1;
q.push({j,(t.i+1)%k,t.nw_t});
}
}
}
printf("%d",dist[n][0]==inf?-1:dist[n][0]);
return 0;
}
感觉大脑被宇宙射线击中了