Submission

Score: 0

User: Nathako9n

Problemset: C.Love Sick

Language: cpp

Time: 0.008 second

Submitted On: 2026-01-02 10:13:02

#include <bits/stdc++.h>
using namespace std;

#define ll long long

struct State {
    ll w;
    int x, u;
};

struct Cmp {
    bool operator()(const State& a, const State& b) const {
        return a.w < b.w;
    }
};

int n, m, k;
vector<vector<pair<int,int>>> vec;

bool ch(ll mid){
    vector<vector<ll>> dp(n, vector<ll>(k+1, -1e18));
    priority_queue<State, vector<State>, Cmp> pq;

    dp[0][0] = mid;
    pq.push({mid, 0, 0});

    while(!pq.empty()){
        auto cur = pq.top(); pq.pop();
        ll w = cur.w;
        int x = cur.x;
        int u = cur.u;

        if(w < dp[x][u]) continue;

        for(auto [nx, nw] : vec[x]){
            ll tt = w - nw;
            if(tt > 0 && dp[nx][u] < tt){
                dp[nx][u] = tt;
                pq.push({tt, nx, u});
            }

            if(u < k){
                tt = w + nw;
                if(dp[nx][u+1] < tt){
                    dp[nx][u+1] = tt;
                    pq.push({tt, nx, u+1});
                }
            }
        }
    }

    return dp[n-1][k] > 0;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    vec.assign(n, {});

    for(int i = 0; i < m; i++){
        int x, y, w;
        cin >> x >> y >> w;
        vec[x].push_back({y, w});
        vec[y].push_back({x, w});
    }

    ll l = 0, r = 1e9;
    while(l <= r){
        ll mid = (l + r) / 2;
        if(ch(mid)) r = mid - 1;
        else l = mid + 1;
    }

    cout << l;
    return 0;
}