Submission

[PPTSSSSSSSSSSSSSSSSS]

Score: 0

User: Jibhong

Problemset: C.Love Sick

Language: cpp

Time: 1.089 second

Submitted On: 2025-01-05 15:54:29

#include <bits/stdc++.h>
#include <cstdint>
#include <queue>
#include <variant>
using namespace std;

const int maxn=1010;

typedef struct Node{
    int pos,dist,pot,out;
    bool operator>(const Node& other) const {
        return out > other.out;
    }
}Node;

typedef struct Edge{
    int nextpos,dist;
}Edge;

typedef struct Mem{
    int dist=2.1e9,pot=2.1e9;
}Mem;

vector<Edge>edge[maxn];
// priority_queue<Node,vector<Node>,greater<Node>>pq;
queue<Node>pq;
// int visited[maxn];
// bool visited[maxn];
// bool visited[maxn][12];
Mem visited[maxn];

int main(){
    int n,e,p;
    cin>>n>>e>>p;
    int u,v,w;
    for(int i=0;i<n;++i){
        cin>>u>>v>>w;
        edge[u].push_back({v,w});
        edge[v].push_back({u,w});
    }
    pq.push({0,0,p,0});
    int out=2.1e9;
    while(!pq.empty()){
//         Node nownode=pq.top();
        Node nownode=pq.front();
        pq.pop();
//         if(visited[nownode.pos].dist<nownode.dist&&visited[nownode.pos].pot<nownode.pot)continue;
        visited[nownode.pos].dist=nownode.dist;
        visited[nownode.pot].pot=nownode.pot;
//
//         cout<<nownode.pos<<' '<<nownode.dist<<' '<<nownode.pot<<' '<<nownode.out<<'\n';
        if(nownode.pos==n-1){
//             cout<<nownode.out+1<<'\n';
//             return 0;
            out=min(out,nownode.out);
        }

        for(auto e:edge[nownode.pos]){
            if(visited[e.nextpos].dist>nownode.dist+e.dist || visited[e.nextpos].pot<nownode.pot)
//                 if(nownode.pot!=0)
                    pq.push({e.nextpos,nownode.dist+e.dist,nownode.pot,max(nownode.out,nownode.dist+e.dist)});

            if(nownode.pot)
                if(visited[e.nextpos].dist>nownode.dist-e.dist || visited[e.nextpos].pot<nownode.pot-1)
                    pq.push({e.nextpos,nownode.dist-e.dist,nownode.pot-1,max(nownode.out,nownode.dist-e.dist)});
        }
    }
    cout<<out+1;
    return 0;
}