Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: Jibhong

Problemset: C.Love Sick

Language: cpp

Time: 0.011 second

Submitted On: 2025-03-27 11:26:48

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
using ll = long long;
using pii =  pair<int,int>;
using plpii = pair<int,pii>;
vector<pii>edge[1005];
int n,m,q;
bool ok(int x){
    bool visited[1005][11]={};
    vector<vector<int>> dist(1005,vector<int>(11,1e9));
    priority_queue<plpii,vector<plpii>,greater<plpii>>pq;
    dist[0][q]=0;
    pq.push({0,{0,q}});
    while(!pq.empty()){
        ll nowdist=pq.top().first;
        auto [nownode,pot]=pq.top().second;
        pq.pop();
        if(nowdist>=x)continue;
        if(nownode==n-1)return 1;
        for(auto e:edge[nownode]){
            auto [tonode,todist]=e; 
            if(dist[tonode][pot]>dist[nownode][pot]+todist && dist[nownode][pot]+todist<x){
                dist[tonode][pot]=dist[nownode][pot]+todist;
                pq.push({dist[tonode][pot],{tonode,pot}});
            }
            if(!pot)continue;
            if(dist[tonode][pot-1]>dist[nownode][pot]-todist){
                dist[tonode][pot-1]=dist[nownode][pot]-todist;
                pq.push({dist[tonode][pot-1],{tonode,pot-1}});
            }
        }
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>q;
    for(int i=0;i<m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        edge[u].emplace_back(v,w);
        edge[v].emplace_back(u,w);
    }
    int ll=1,rr=1e9;
    while(ll<rr){
        int mm=(ll+rr)/2;
//         cout<<ok(mm)<<'<'<<mm<<'\n';
        if(ok(mm))rr=mm;
        else ll=mm+1;
    }
    cout<<ll;
    return 0;
}