TOI13: Budget Travelling

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
using pi=pair<int,int>;
using pii=pair<int,pi>;

int n,m,x,y,z;
vector <pi> g[100001];
set <pi> way;

bool dijk1(){
    vector <int> dis(n+1,INF);
    vector <bool> visited(n+1,false);
    priority_queue <pi,vector<pi>,greater<pi>> pq;
    dis[x]=0;
    pq.push({0,x});
    while(pq.size()>0){
        int u,d;
        d=pq.top().first;
        u=pq.top().second;
        pq.pop();

        if(visited[u])
            continue;
        visited[u]=true;

        if(u==y) {
            printf("%d %d 0",y,d);
            return true;
        }

        for(auto vw:g[u]){
            int v,w;
            v=vw.first;
            w=vw.second;
            if(!visited[v] and d+w<dis[v] and d+w<=z){
                dis[v]=d+w;
                pq.push({d+w,v});
            }
            else if(!visited[v] and d+w<dis[v] and d+w>z) {
                way.insert({u,dis[u]});
            }
        }
    }
    return false;
}
int dijk2(int u){
    vector <int> dis(n+1,INF);
    vector <bool> visited(n+1,false);
    priority_queue <pi,vector<pi>,greater<pi>> pq;
    dis[u]=0;
    pq.push({dis[u],u});
    while(pq.size()>0){
        int d;
        d=pq.top().first;
        u=pq.top().second;
        pq.pop();

        if(visited[u])
            continue;
        visited[u]=true;

        if(u==y){
            return d;
        }

        for(auto vw:g[u]){
            int v,w;
            v=vw.first;
            w=vw.second;
            if(!visited[v] and d+w<dis[v]){
                dis[v]=d+w;
                pq.push({d+w,v});
            }
        }

    }
}
int main(){

    scanf("%d%d%d%d%d",&n,&m,&x,&y,&z);

    for(int i=0;i<m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }

    int node,mn=INF,dis;
    if( !dijk1() ) {
        for(auto w:way){
            int D=dijk2(w.first);
            if(D<mn){
                mn=D;
                node=w.first;
                dis=w.second;
            }
        }
        printf("%d %d %d",node,dis,mn);
    }


    return 0;
}
/*

8 11 0 5 200 0 1 10 0 2 10 1 3 10 1 5 70 2 3 10 2 4 30 2 6 10 3 5 30 4 5 20 6 7 15 7 5 20

8 11 0 5 45 0 1 10 0 2 10 1 3 10 1 5 70 2 3 10 2 4 30 2 6 10 3 5 30 4 5 20 6 7 15 7 5 20
*/