Submission

[PP-SSSSSSSSSSSSSSSSS]

Score: 0

User: njoop

Problemset: C.Love Sick

Language: cpp

Time: 0.029 second

Submitted On: 2025-01-05 17:44:27

#include <bits/stdc++.h>
#define int long long
#define ti tuple<int, int, int>
using namespace std;

int n, m, k, u, v, w;
vector<pair<int, int>> g[1010];
priority_queue<ti> pq;
int dis[1010][11];

bool solve(int val) {
    for(int i=0; i<1010; i++) {
        for(int j=0; j<11; j++) {
            dis[i][j] = 0;
        }
    }
    dis[0][0] = val;
    pq.push({val, 0, 0});
    while(pq.size()) {
        int cw = get<0>(pq.top());
        int cn = get<1>(pq.top());
        int cl = get<2>(pq.top());
        pq.pop();
        if(dis[cn][cl] > cw || cl > k || cw < 0) continue;
        dis[cn][cl] = cw;
        for(auto i: g[cn]) {
            int nn = i.first;
            int nw = i.second;
            if(cw-nw > dis[nn][cl] && cw-nw > 0) {
                dis[nn][cl] = cw-nw;
                pq.push({cw-nw, nn, cl});
            }
            if(cw+nw > dis[nn][cl+1] && cw+nw > 0) {
                dis[nn][cl+1] = cw+nw;
                pq.push({cw+nw, nn, cl+1});
            }
        }
    }
    return !dis[n-1][k];
}

signed main() {
    cin >> n >> m >> k;
    int l=0, r=1e18;
    while(m--) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    while(l < r) {
        int mid = (l+r)/2;
        if(solve(mid)) {
            l = mid+1;
        } else {
            r = mid;
        }
    }
    cout << l;
    return 0;
}