图论、贪心、最短路

想复杂了。

由于坐车任何时候都比走路快，所以能坐车的时候一定是坐车的。

令 $dis_i$ 为从 $i$ 出发在时限内到达 $n$ 的最晚出发时间，从 $n$ 开始跑最短路，如果能够坐车扩展到下一节点则坐车，否则在走路和原地等待中取较优决策扩展到下一节点。

由于 $n,m$ 同阶，时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
constexpr long long inf=1'000'000'000'000'000'000ll;
struct Edge{
    int to;long long dis;
    Edge(int x,long long y):to(x),dis(y){}
    bool operator<(const Edge &x)const{
        return this->dis>x.dis;
    }
};
struct Star{int w,v,to;Star(int x,int y,int z):w(x),v(y),to(z){}};
long long E,L,R,dis[100'005];
vector<Star> v[100'005];
bool on[100'005];
int n,m;
void solution(){
    cin>>n>>m>>E>>L>>R;
    for(int i=1;i<=n;i++) on[i]=0,dis[i]=inf,v[i].clear();
    for(int i=1;i<=m;i++){
        static int x,y,l,r;
        cin>>x>>y>>l>>r;
        v[x].push_back(Star(l,r,y));
        v[y].push_back(Star(l,r,x));
    }
    dis[n]=0ll;
    priority_queue<Edge> q;
    q.push(Edge(n,dis[n]));
    while(!q.empty()){
        int now=q.top().to;q.pop();
        if(on[now]) continue;
        on[now]=1;
        for(auto i:v[now]){
            if(dis[now]>=E-L||dis[now]+i.w<=E-R){
                if(dis[now]+i.w<dis[i.to]){
                    dis[i.to]=dis[now]+i.w;
                    q.push(Edge(i.to,dis[i.to]));
                }
            }
            else{
                long long nxt=min(dis[now]+i.v,E-L+i.w);
                if(nxt<dis[i.to]){
                    dis[i.to]=nxt;
                    q.push(Edge(i.to,nxt));
                }
            }
        }
    }
    cout<<max(E-dis[1],-1ll)<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}