Submission

[PP-SSSSSSSSSSSSSSSSS]

Score: 0

User: KotatsuCat

Problemset: C.Love Sick

Language: cpp

Time: 0.015 second

Submitted On: 2025-01-07 18:48:33

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,ll>
#define tpi tuple<int,int,int>

using namespace std;

const int mxN = 1001;
const int mxK = 11;
const ll inf = 1e18;
ll dist[mxN][mxK], n, k;
bool vis[mxN][mxK];
vector<pii> g[mxN];

bool check(ll m){
	for(int i=0;i<n;i++) for(int j=0;j<=k;j++) dist[i][j]=inf, vis[i][j] = false;
	vis[0][0]=true;
	dist[0][0]=0;
	for(int kk=0;kk<=k;kk++){
		for(int i=0;i<n-1;i++){
			for(int j=0;j<n;j++){
				if(!vis[j][kk]) continue;
				for(auto &[v, w]:g[j]){
					//not use
					if(m-dist[j][kk]-w>0 && dist[v][kk]>dist[j][kk]+w) dist[v][kk] = dist[j][kk]+w, vis[v][kk]=true;
					//use
					if(kk+1<=k && dist[v][kk+1]>dist[j][kk]-w) dist[v][kk+1]=dist[j][kk]-w, vis[v][kk+1]=true;
				}
			}
			if(vis[n-1][kk]) return true;
		}
	}
	return false;
}


int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int m;
	cin >> n >> m >> k;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}
	ll l = 0, r = 1e18;
	while(l<r){
		ll mid = (l+r)/2;
		if(!check(mid)) l = mid+1;
		else r = mid;
	}
	cout << l;
	
	return 0;
}