Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: ftm

Problemset: C.Love Sick

Language: cpp

Time: 0.009 second

Submitted On: 2025-01-10 20:30:50

#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b,c) for(int i=a;i<=b;i+=c)
#define r(i,a,b,c) for(int i=a;i>=b;i-=c)
#define fi first
#define se second
#define pb push_back
using ll=long long int;
using a2=array<int,2>;
const int N=1e3+3;
const int M=1e9+7;
const int K=11;
const int inf=1e9;
vector<a2> g[N];
vector<vector<bool>> inq;
int n,m,k;
int d[N][K];

bool solve(int m){
	//cout<<"M = "<<m<<"\n\n";
	f(i,1,n,1){
		f(j,0,k,1) d[i][j]=inf;
	}
	inq.resize(n+1);
	f(i,1,n,1){
		inq[i].assign(k+1,0);
	}
	queue<a2> q;
	q.push({1,0});
	inq[1][0]=1;
	d[1][0]=0;
	while(!q.empty()){
		int u=q.front()[0];
		int l=q.front()[1];
		//cout<<u<<" "<<l<<" "<<d[u][l]<<"\n";
		q.pop();
		inq[u][l]=0;
		if(u==n) return 1;
		for(auto e:g[u]){
			int v=e[0],w=e[1];
			int x=d[u][l]+w;
			if(x<m && x<d[v][l]){
				d[v][l]=x;
				if(!inq[v][l]) {
					q.push({v,l});
					inq[v][l]=1;
				}
			}
		}
		if(l<k){
			for(auto e:g[u]){
				int v=e[0],w=e[1];
				int x=d[u][l]-w;
				if(x<d[v][l+1]){
					d[v][l+1]=x;
					if(!inq[v][l+1]) {
						q.push({v,l+1});
						inq[v][l+1]=1;
					}
				}
			}
		}
	}
	return 0;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m>>k;
	f(i,1,m,1){
		int u,v,w;
		cin>>u>>v>>w;
		u++,v++;
		g[u].pb({v,w});
		g[v].pb({u,w});
	}
	int l=1,r=1e9;
	while(l<r){
		int m=(l+r)/2;
		bool x=solve(m);
		if(x){
			r=m;
		}
		else{
			l=m+1;
		}
	}
	cout<<l;
}
/*
6 6 1
0 1 1
1 2 2
2 3 1
2 4 5
3 4 1
4 5 3

*/