Submission

Score: 0

User: Nathako9n

Problemset: C.Love Sick

Language: cpp

Time: 0.002 second

Submitted On: 2026-01-02 10:16:59

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

#define ll long long
#define endl '\n'

int n, m, k;
const ll INF = (ll)1e18;

vector<pair<int,int>> vec[1005];

struct State {
    ll w;
    int x, u;
    bool operator<(State const& other) const {
        return w < other.w;
    }
};

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

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

    while (!pq.empty()) {
        auto [w, x, u] = pq.top();
        pq.pop();

        if (w != dp[x][u]) continue;
        if (x == n-1) return true;

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

            if (u < k) {
                ll nw_energy = w + nw;
                nw_energy = min(nw_energy, INF);
                if (nw_energy > dp[nx][u+1]) {
                    dp[nx][u+1] = nw_energy;
                    pq.push({nw_energy, nx, u+1});
                }
            }
        }
    }
    return false;
}

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

    cin >> n >> m >> k;
    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 = 1e6;
    while (l < r) {
        ll mid = (l + r) / 2;
        if (ch(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << endl;
    return 0;
}