Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: rtnz

Problemset: C.Love Sick

Language: cpp

Time: 0.018 second

Submitted On: 2025-01-05 18:10:14

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

int N, M, K;
vector<pii> G[1005];
bool f(ll x) {
    priority_queue<ti > pq;
    pq.push({x, 0, K});
    ll dist[1005][15]={0};
    for (int i=0; i<N; i++) for(int j=0; j<=K; j++) dist[i][j] = -1e15;
    dist[0][K] = x;
    
    while (!pq.empty()) {
        auto [H, CR, KX] = pq.top(); pq.pop();
        if (H < dist[CR][KX]) continue;
        dist[CR][KX] = H;
        if (CR == N-1) {
            return true;
        }

        if (H <= 0) continue;
        
        for (auto [next,cost]: G[CR]) {
//            cout << next << ' ' << cost << '\n';
            if (H-cost>0&&H-cost>=dist[next][KX]) {
//                vis[{H+cost, next, KX-1}]=true;
                dist[next][KX]=H-cost;
                pq.push({H-cost, next, KX});
            }
            if(KX>0&&H+cost>=dist[next][KX-1]) {
//                vis[{H+cost, next, KX-1}]=true;
                dist[next][KX-1]=H+cost;
                pq.push({H+cost, next, KX-1});
            }
        } 
    }
    return false;
}
int main() {
    cin >> N>>M>>K;
    for (int i=0, u,v, w; i<M; i++) {
        cin >> u>>v>> w;
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }

    ll L = 1;
    ll R = 10000000001;
//    f(4);
    while (L<R) {
        ll M = (L+R)/2;
        if (f(M)) {
            R = M;
        } else {
            L = M+1;
        }
    }
    printf("%d", L);
}