SMMR-T167: Grandiosity

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

typedef long long lli;
typedef pair<lli, int> pli;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int N = 1e4;

vector<pii> adj[N + 10], rev[N + 10];
vector<lli> dist[2];
vector<tiii> edges;
int nVertex;

void Dijkstra(int st, int i){
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    vector<bool> visited(nVertex + 1, false);
    dist[i].assign(nVertex + 1, 1e18);
    dist[i][st] = 0;
    pq.emplace(0, st);
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(visited[u]){
            continue;
        }
        visited[u] = true;
        for(pii p : (i == 0)? adj[u] : rev[u]){
            int v = p.first;
            int w = p.second;
            if(!visited[v] && dist[i][u] + w < dist[i][v]){
                dist[i][v] = dist[i][u] + w;
                pq.emplace(dist[i][v], v);
            }
        }
    }
}

int main(){

    int nEdge, st, ed;
    lli lim;
    scanf("%d%d%d%d%lld", &nVertex, &nEdge, &st, &ed, &lim);

    for(int i = 1; i <= nEdge; ++i){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].emplace_back(v, w);
        rev[v].emplace_back(u, w);
        edges.emplace_back(w, u, v);
    }

    Dijkstra(st, 0);
    Dijkstra(ed, 1);

    int mx = -1;
    for(tiii e : edges){
        int w = get<0>(e);
        int u = get<1>(e);
        int v = get<2>(e);
        lli sum = dist[0][u] + w + dist[1][v];
        if(sum <= lim){
            mx = max(mx, w);
        }
    }

    cout << mx;

    return 0;
}