题解 | #游游的正方形披萨#

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,hh;
struct edge{
    int to,ne,w,d;
}e[3*N];
int dis[N],h[N],cnt,vis[N];
void add(int u,int v,int w,int d){
    cnt++;
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].ne=h[u];
    e[cnt].d=d;
    h[u]=cnt;
}
struct xx{
    int dis,pos;
    bool operator <(const xx &a) const{
        return a.dis<dis;
    }
};

int dijkstr(int mid){
    priority_queue<xx> q;
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    q.push({0,1});
    dis[1]=0;
    while(!q.empty()){
        auto t=q.top();
        q.pop();
        int x=t.pos;
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=h[x];i;i=e[i].ne){
            int y=e[i].to;
            if(e[i].w<mid) continue;
            if(dis[y]>dis[x]+e[i].d){
                dis[y]=dis[x]+e[i].d;
                q.push({dis[y],y});
            }
        }
    }
    return dis[n]<=hh;
}
int main(){
    cin>>n>>m>>hh;
    for(int i=0;i<m;i++){
        int u,v,w,d;
        cin>>u>>v>>w>>d;
        add(u,v,w,d);
        add(v,u,w,d);
    }
    int l=0,r=2e9;
    while(l<r){
        int mid=l+r+1>>1;
        if(dijkstr(mid)) l=mid;
        else r=mid-1;
    }
    if(dijkstr(l)) cout<<l;
    else cout<<-1;
}