Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: Monasm

Problemset: C.Love Sick

Language: cpp

Time: 0.014 second

Submitted On: 2025-01-06 09:03:27

#include <iostream>
#include <cstdint>
#include <cstring>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <numeric>
#include <array>
#include <iomanip> // cout << fixed << setprecision(n);

using namespace std;
const bool TEST_CASE = 0;

template<typename T>
typename std::enable_if<std::is_integral<T>::value>::type
Debug(const char* name, T value) {
    std::cout << name << " : " << value << '\n';
}

template<typename T, typename... Args>
typename std::enable_if<std::is_integral<T>::value>::type
Debug(const char* names, T value, Args... args) {
    const char* comma = strchr(names, ',');
    std::cout.write(names, comma - names) << " : " << value << " | ";
    Debug(comma + 1, args...);
}
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {
    for(auto &x : a) out << x << ' '; 
    return out;
};

#ifdef DORMON
    #define debug(...) Debug(#__VA_ARGS__, __VA_ARGS__)
#else
    #define debug(...) 
#endif

struct heap{
    int u, w, use;
    bool operator < (const heap &o) const {
        return w > o.w;
    }
};

const int inf = 1e9+7;

void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0;i < m;i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    auto check = [&](int hp) -> bool {
        vector<vector<int>> dist(n, vector<int>(k+1, inf));
        dist[0][0] = 0;
        bool change = true;
        for (int t = 0;t < n-1 && change;t++){
            change = false;
            for (int state = 0;state <= k;state++){
                for (int u = 0;u < n;u++){
                    if (dist[u][state] == inf) continue;
                    for (auto [v, w]:adj[u]){
                        if (dist[u][state] + w < dist[v][state] && dist[u][state] + w < hp){
                            dist[v][state] = dist[u][state] + w;
                            change = true;
                        }
                    }
                    if (state < k){
                        for (auto [v, w]:adj[u]){
                            if (dist[u][state] - w < dist[v][state+1]){
                                dist[v][state+1] = dist[u][state] - w;
                                change = true;
                            }
                        }
                    }
                }
            }
        }
        for (int i = 0;i <= k;i++)
            if (dist[n-1][i] != inf)
                return true;
        return false;
    };

    int lb = 1, ub = 1e9, ans = 0;
    while (lb <= ub){
        int mid = lb + (ub - lb) / 2;
        if (check(mid)){
            ans = mid;
            ub = mid - 1;
        }
        else
            lb = mid + 1;
    }
    cout << ans << '\n';
}


int main()
{
    #ifndef DORMON
        ios_base::sync_with_stdio(false); 
    #endif
    cin.tie(0);
    int q = 1; 
    if (TEST_CASE) cin >> q;
    while (q--){
        solve();
    }
}