题目不用贴了吧
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
const int maxm=2e4+5;
const int maxk=1e2+5;
const int inf=1e7;
struct edge{
int to,next,w;
};
int n,m,k,u,v,w,cnt;
int head[maxn*maxk];
edge e[maxm*maxk];
void add_edge(int u,int v,int w){
e[++cnt].to=v;
e[cnt].next=head[u];
e[cnt].w=w;
head[u]=cnt;
}
queue<int> q;
int dis[maxn * maxk];
void bfs(int d){
memset(dis,-0x3f,sizeof(dis));
q.push(n);
dis[n]=d;
while(!q.empty()){
int v=q.front();
q.pop();
for(int i=head[v];i;i=e[i].next){
int u=e[i].to;
if(dis[v]>e[i].w&&dis[u]==dis[0]){
dis[u]=dis[v]-1;
q.push(u);
}
}
}
}
int main(){
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
for(int j=0;j<k-1;j++){
add_edge(v+(j+1)*n,u+j*n,w);
add_edge(v,u+(k-1)*n,w);
}
}
bfs(inf);
if(dis[1]<0){
printf("-1");
return 0;
}
int l=0,r=inf;
while(l<r){
int mid=(l+r)>>1;
bfs(mid);
if(dis[1]>=0) r=mid;
else l=mid+1;
}
bfs(l);
printf("%d",l+(dis[1]+k-1)/k*k-dis[1]);
return 0;
}
()