Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: fluke

Problemset: C.Love Sick

Language: cpp

Time: 0.014 second

Submitted On: 2025-03-22 19:57:41

#include <bits/stdc++.h>
#define ll long long 
#define f first
#define s second 
#define pii pair<int,ll>
#define emb emplace_back
#define em emplace 
#define all(x) x.begin(),x.end()
#define sp <<" "<<
#define DB cout<<"\n";system("pause");
using namespace std;

int di[]={0,1,0,-1,1,1,-1,-1};
int dj[]={1,0,-1,0,1,-1,1,-1};
int inf = 2e9;
ll INF = 2e18;
int mod = 1e9 + 7;

int n,m,k;

struct state{
    ll dis;
    int skip;
    int node;

    state(ll _dis , int _skip , int _node){
        dis = _dis;
        skip = _skip;
        node = _node;
    }
};

struct cmp{

    bool operator()(const state &a , const state &b){
        return a.dis > b.dis;
    }

};

bool can(ll mid ,vector <vector <pii>> &adj){
    priority_queue <state , vector <state> , cmp > pq;
    vector <vector <ll> > dis(k+1,vector <ll> (n,INF)); 
    pq.em(0,k,0);

    while(!pq.empty()){
        auto [dis_now , skip_now , node_now] = pq.top();
        pq.pop();

        if(dis[skip_now][node_now] <= dis_now || dis_now >= mid)continue;
        if(node_now == n-1)return true;
        dis[skip_now][node_now] = dis_now;

        for(auto [next_node , weight] : adj[node_now]){
            
            ll next_dis = dis_now + weight;

            if(skip_now != 0){
                if(dis[skip_now - 1][next_node] > dis_now - weight && dis_now - weight < mid){
                    pq.em(dis_now - weight , skip_now - 1 ,next_node);
                }
            }

            if(dis[skip_now][next_node] <= next_dis || next_dis >= mid)continue;
            pq.em(next_dis,skip_now,next_node);

        }
    }

    return false;

}


int main(){
ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m>>k;
    vector <vector <pii>> adj(n);
    for(int i=0;i<m;i++){
        int x,y;
        ll z;
        cin>>x>>y>>z;
        adj[x].emb(y,z);
        adj[y].emb(x,z);
    }

    ll ans = 0;
    ll left = 0 , right = 1e9;
    while(left <= right){
        ll mid = (left + right)/2;

        // cout<<left sp right<<"\n";
        // cout<<mid;
        // DB

        if(can(mid , adj)){
            ans = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }

    cout<<ans;


}