CUBE-151: Marathon

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
using pii=pair<int,int>;
struct node{
    int v,d,t;
};
int f(vector <node> g[],int D,int n,int T){
    vector <bool> visited(n+1,false);
    vector <int> dis(n+1,INF);
    priority_queue <pii,vector<pii>,greater<pii>> pq;
    dis[1]=0;
    pq.push({dis[1],1});
    while(pq.size()>0){
        int u,dist;
        u=pq.top().second;
        dist=pq.top().first;
        pq.pop();
        if(visited[u] or dist>T)
            continue;
        visited[u]=true;
        if(u==n)
            return dist;
        for(auto vdt:g[u]){
            int v,d,t;
            v=vdt.v;
            d=vdt.d;
            t=vdt.t;
            if(!visited[v] and d<=D and dis[u]+t<dis[v]){
                dis[v]=dis[u]+t;
                pq.push({dis[v],v});
            }
        }
    }
    return INF;
}
int main(){

    int n,m,k,T;
    scanf("%d%d%d%d",&n,&m,&k,&T);
    vector <node> g[n+1];

    int l=INF,r=-INF,mid;
    for(int i=1;i<=m;i++){
        int u,v,d,t;
        scanf("%d%d%d%d",&u,&v,&d,&t);
        g[u].push_back({ v,d,t });
        g[v].push_back({ u,d,t });
        l=min(l,d);
        r=max(r,d);
    }

    int mn=INF;
    while(l<=r){
        mid=(l+r)/2;
        if( f(g,mid,n,T)<=T ){
            r=mid-1;
            mn=min(mn,mid);
        }
        else l=mid+1;
    }
    int ans=INF;
    for(int i=1;i<=k;i++){
        int p,s;
        scanf("%d%d",&p,&s);
        if(s>=mn) ans=min(ans,p);
    }

    if(ans==INF) printf("-1");
    else printf("%d",ans);

    return 0;
}