Submission

[PP-SSSSSSSSSSSSSSSSS]

Score: 0

User: mydKN

Problemset: C.Love Sick

Language: cpp

Time: 0.008 second

Submitted On: 2025-03-27 10:36:43

#include<bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

struct stc{
	int w, t, u;
};

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

int n, m, k;
vector<pii> adj[maxn];
bool visited[maxn][maxk];
int low, high, res;

bool ok(int h){
	queue<stc> qu;
	qu.push({h, 0, 0});
	while(!qu.empty()){
		auto [uw, ut, u] = qu.front();
		qu.pop();
		if(u == n-1) return 1;
		for(auto [vw, v] : adj[u]){
			if(ut < k) qu.push({uw + vw, ut + 1, v});
			if(uw > vw) qu.push({uw - vw, 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);
		high += w;
	}
	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;
}