SMMR-T154: Journey

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long lli;

typedef struct edge{
    int v;
    lli w;
    bool operator < (const edge &rhs)const{
        return w > rhs.w;
    }
}edge;

vector<vector<edge>> adj;
int nv, ne;
lli lim;

int Dijkstra(int start){
    priority_queue<edge> q;
    vector<bool> visited(nv + 1, false);
    vector<lli> dist(nv + 1, 1e18);
    int mx = 1;
    visited[start] = true;
    dist[start] = 0;
    q.push({start, dist[start]});
    while(!q.empty()){
        edge tmp;
        tmp.v = q.top().v;
        tmp.w = q.top().w;
        q.pop();
        if(visited[tmp.v] && tmp.v != start){
            continue;
        }
        visited[tmp.v] = true;
        if(dist[tmp.v] <= lim){
            mx = max(mx, tmp.v);
        }
        for(auto nxt : adj[tmp.v]){
            if(!visited[nxt.v] && dist[tmp.v] + nxt.w < dist[nxt.v]){
                dist[nxt.v] = dist[tmp.v] + nxt.w;
                q.push({nxt.v, dist[nxt.v]});
            }
        }
    }
    return mx;
}

int main(){

    int u, v, w;

    scanf("%d %d %lld", &nv, &ne, &lim);
    adj.assign(nv + 1, vector<edge>());
    for(int i = 1; i <= ne; ++i){
        scanf("%d %d %d", &u, &v, &w);
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    cout << Dijkstra(1);

    return 0;
}