Submission

[P-SSSSSSSSSSSSSSSSSS]

Score: 0

User: Nathlol2

Problemset: C.Love Sick

Language: cpp

Time: 0.004 second

Submitted On: 2025-03-03 22:00:19

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using namespace std;
const int N = 1005;
vector<vector<pii>> g(N);
int n, m, k;

bool ok(int x) {
    vector<vector<int>> dist(n + 1, vector<int>(k + 1, -1e9));
    priority_queue<pair<int, pii>> pq;

    dist[0][0] = x;
    pq.push({x, {0, 0}});

    while (!pq.empty()) {
        int e = pq.top().first;
        auto [u, c] = pq.top().second;
        pq.pop();

        if (e < dist[u][c])
			continue;

        for (auto [v, w] : g[u]) {
            if (e >= w && e - w > dist[v][c]) {
                dist[v][c] = e - w;
                pq.push({e - w, {v, c}});
            }
            if (c < k && e + w > dist[v][c + 1]) {
                dist[v][c + 1] = e + w;
                pq.push({e + w, {v, c + 1}});
            }
        }
    }
	int mx = -1e9;
	for(int i = 0;i<=k;i++){
		mx = max(mx, dist[n - 1][i]);
	}
	if(mx > 0)
		return true;
	else
		return false;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].pb({b, w});
        g[b].pb({a, w});
    }
    int l = 0, r = 1e9, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (ok(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
	cout << ans + 1 << '\n';
}