Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: KotatsuCat

Problemset: C.Love Sick

Language: cpp

Time: 0.019 second

Submitted On: 2025-01-07 19:10:30

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

using namespace std;

const int mxN = 1001;
const int mxK = 11;
const int inf = 1e9+1;
int dist[mxN][mxK], n, k;
vector<pii> g[mxN];

bool check(int m){
	priority_queue<tpi, vector<tpi>, greater<tpi>> q;
	for(int i=0;i<n;i++) for(int j=0;j<=k;j++) dist[i][j]=inf;
	q.emplace(dist[0][0]=0, 0, 0);
	while(!q.empty()){
		auto [d, u, kk] = q.top();
		q.pop();
		if(u==n-1) return true;
		for(auto &[v, w]:g[u]){
			//not use
			if(m>d+w && dist[v][kk]>d+w){
				dist[v][kk] = d+w;
				q.emplace(dist[v][kk], v, kk);
			}
			//use
			if(kk+1<=k && dist[v][kk+1]>d-w){
				dist[v][kk+1] = d-w;
				q.emplace(dist[v][kk+1], v, kk+1);
			}
		}
	}
	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);
	}
	int l = 1, r = 1e9+1;
	while(l<r){
		int mid = (l+r)/2;
		if(!check(mid)) l = mid+1;
		else r = mid;
	}
	cout << l;
	
	return 0;
}