Submission

[P-SSSSSSSSSSSSSSSSSS]

Score: 0

User: Jibhong

Problemset: C.Love Sick

Language: cpp

Time: 0.007 second

Submitted On: 2025-03-27 09:45:54

#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<ll,pii>;
vector<pii>edge[1005];
bool visited[1005][11];
vector<vector<ll>> dist(1005,vector<ll>(1005,9e18));
priority_queue<plpii,vector<plpii>,greater<plpii>>pq;
int main(){
    int n,m,q;
    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);
    }
    dist[0][q]=0;
    pq.push({0,{0,q}});
    while(!pq.empty()){
        auto [nownode,pot]=pq.top().second;
        pq.pop();
        if(visited[nownode][pot])continue;
        visited[nownode][pot]=1;
        for(auto e:edge[nownode]){
            auto [tonode,todist]=e;
            if(dist[tonode][pot]>dist[nownode][pot]+todist && !visited[tonode][pot]){
                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 && !visited[tonode][pot-1]){
                dist[tonode][pot-1]=dist[nownode][pot]-todist;
                pq.push({dist[tonode][pot-1],{tonode,pot-1}});
            }
        }
    }
    ll out=9e18;
    for(auto e:dist[n-1]){
        out=min(out,e);
    }
    cout<<out;
    return 0;
}