Submission

[PP-SSSSSSSSSSSSSSSSS]

Score: 0

User: mydKN

Problemset: C.Love Sick

Language: cpp

Time: 0.004 second

Submitted On: 2025-03-27 10:55:39

#include<bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

struct stc{
	int w, t, u;
	bool operator<(const stc& a) const{
		if(w != a.w) return w < a.w;
		return t > a.t;
	}
};

const int maxn = 1e3 + 10;
const int maxk = 15;
const int inf = 2e9;

int n, m, k;
vector<pii> adj[maxn];
int low, high = 1e9, res;

bool ok(int h){
	int dist[n+5][k+5];
	priority_queue<stc> pq;
	for(int i=0;i<n;++i){
		for(int j=0;j<=k;++j){
			dist[i][j] = 0;
		}
	}
	pq.push({h, 0, 0});
	dist[0][0] = h;
	while(!pq.empty()){
		auto [uh, ut, u] = pq.top();
		pq.pop();
		if(uh < dist[u][ut]) continue;
		if(u == n-1) return 1;
		for(auto [vw, v] : adj[u]){
			if(ut < k && dist[v][ut + 1] < dist[u][ut] + vw){
				dist[v][ut + 1] = dist[u][ut] + vw;
				pq.push({dist[v][ut + 1], ut + 1, v});
			}
			if(dist[u][ut] > vw && dist[v][ut] < dist[u][ut] - vw){
				dist[v][ut] = dist[u][ut] - vw;
				pq.push({dist[v][ut], ut, v});
			}
		}
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m >> k;
	for(int i=0;i<m;++i){
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].emplace_back(w, v);
		adj[v].emplace_back(w, u);
	}
	while(low <= high){
		int mid = (low + high) / 2;
		// cout << mid << " ";
		if(ok(mid)){
			high = mid - 1;
			res = high;
		}
		else{
			low = mid + 1;
		}
	}
	cout << res + 1;
}