Submission

Score: 0

User: Nathako9n

Problemset: C.Love Sick

Language: cpp

Time: 0.009 second

Submitted On: 2026-01-02 10:11:32

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define pii tuple<ll,int,int>
using namespace std;
int n,m,k;
const int N = 1e3+4;
vector<pair<int,int>> vec[N+2];
bool ch(int mid){
    vector<vector<ll>> dp(n+1,vector<ll>(k+1,-1e15));
    priority_queue<pii> pq;
    pq.push({mid,0,0});
    dp[0][0]=mid;
    while(!pq.empty()){
            auto[w,x,u]=pq.top();pq.pop();
            if(w<dp[x][u])continue;
            for(auto [nx,nw]:vec[x]){
                ll tt=w-nw;
                if(tt>0&&dp[nx][u]<tt){
                    dp[nx][u]=tt;
                    pq.push({tt,nx,u});
                }
                if(u<k){
                    tt=w+nw;
                    if(dp[nx][u+1]<tt){
                        dp[nx][u+1]=tt;
                        pq.push({tt,nx,u+1});
                    }
                }
            }
    }
    return dp[n-1][k]>0?(1):(0);

}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int x,y,w;cin>>x>>y>>w;
        vec[x].push_back({y,w});
        vec[y].push_back({x,w});
    }
    int l=0,r=1e6+2;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(ch(mid))r=mid-1;
        else l=mid+1;
    }
    cout<<l;
}

/*


*/