beskar.cpp

/*
Solution for full marks uses binary search
*/

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define f first
#define s second
#define what_is(a) cout << #a << " is " << a << "\n";


using namespace std;

inline void io(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);
}

const int MAX_SIZE = 3000;

int n,m,T;
vector<vector<int>> adjList(MAX_SIZE,vector<int>());
ll t[MAX_SIZE][MAX_SIZE];
ll h[MAX_SIZE][MAX_SIZE];
ll dis[MAX_SIZE];
bool visited[MAX_SIZE];

inline ll max(ll a,ll b){
    return a<b?b:a;
}

inline ll min(ll a,ll b){
    return a<b?a:b;
}


void dijsktra(int src){
    for(int i=0;i<n;i++)dis[i] = INT_MAX;
    dis[src] = 0;
    while(true){
        int u=-1;ll dd=INT_MAX;
        for(int i=n-1;i>=0;i--){
            if(!visited[i]){
                if(dis[i]<=dd&&dis[i]>=0){u=i,dd=dis[i];}}}
        if(u==-1)break;
        visited[u]=true;
        for(int v:adjList.at(u)){
            if(dis[u]+t[u][v] <= dis[v]){
                dis[v] = dis[u]+t[u][v];
            }
        }
    }
}

ll temp[MAX_SIZE];
ll ddd[MAX_SIZE];

void dijsktra_t(int src){
    for(int i=0;i<n;i++)temp[i] = INT_MAX,visited[i]=false,ddd[i]=0;
    temp[src] = 0,ddd[src]=0;
    while(true){
        int u=-1;ll tt=INT_MAX;
        for(int i=n-1;i>=0;i--){
            if(!visited[i]){
                if(temp[i]<tt && temp[i]>=0){u=i,tt=temp[i];}}}
        if(u==-1)break;
        visited[u]=true;
        for(int v:adjList.at(u)){
            if(T-(ddd[u]+t[u][v])>=dis[v] && temp[v]>= max(tt,h[u][v])){
                temp[v] = max(tt,h[u][v]);
                ddd[v]=ddd[u]+t[u][v];
            }
        }
    }
}

void solve(){
    cin >> n >> m >> T;
    for(int i=0;i<m;i++){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        adjList.at(a).pb(b);
        adjList.at(b).pb(a);
        t[a][b] = c; t[b][a] = c;
        h[a][b] = d; h[b][a] = d;
    }
    dijsktra(1);
    dijsktra_t(0);
    cout << temp[1] << "\n";
}


int main(){
    io();
    solve();
    return 0;
}