Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: Nathlol2

Problemset: C.Love Sick

Language: cpp

Time: 0.017 second

Submitted On: 2025-03-15 14:01:31

#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, 0));
    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;
		if(u == n - 1)
			return true;
        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}});
            }
        }
    }
	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 = 1, 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 << '\n';
}