Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: Monasm

Problemset: C.Love Sick

Language: cpp

Time: 0.011 second

Submitted On: 2025-03-06 02:59:05

#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});
    }
    if (k == 0) {
        vector<int> dist(n, 1e9);
        dist[n - 1] = 0;
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push({0, n - 1});
        
        while (!pq.empty()) {
            auto [e, u] = pq.top();
            pq.pop();
            if (e > dist[u]) continue;
            for (auto [v, w] : g[u]) {
                if (w + dist[u] < dist[v]) {
                    dist[v] = w + dist[u];
                    pq.push({dist[v], v});
                }
            }
        }
        cout << dist[0] + 1 << '\n';
        return 0;
    }

    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';
}