Solution
我们可以看出的是我们可以在一条边上反复来回来拖延时间。于是我们就可以发现我们可以把边拆成奇偶分开来考虑。
我们可以设 \(f_{u,0/1}\) 表示到点 \(u\) 时间为偶数/奇数的最大时间，那么对于 \(u\) 连出去的一条时间为 \([L,R]\) 到 \(v\) 的边（这个已经按奇偶分开了）存在，当且仅当 \(f_{u,0/1}\ge L\) 的时候会对 \(f_{v,1/0}\) 产生 \(R+1\) 的影响。而且你发现一个严重的问题是，你不一定能在 \(L\) 走到 \(u\)，有可能前面提高了上限。所以我们还要考虑时刻维护下界的变化。
那么维护方案也就呼之欲出了。我们可以把边按 \(L\) 进行排序加入，然后按上面的方法进行更新。但是你会发现对于 \(f_{u,0/1}<L\) 的情况我们有可能后面更新了 \(f_{u,0/1}\) ，所以我们可以先存下来等后面增大了 \(f_{u,0/1}\) 再加进去，那么同时我们也就可以更新它的下界。可以看出来的是每次 \(u\) 更新了 \(v\)，那么 \(v\) 之前残存的边下界会改成 \(L+1\)，\(f_{v,1/0}\) 会变成 \(R\)，所以如果 \(L+1\le R\) 那么一定可以加进去，所以一条边最多被考虑 \(2\) 次。
复杂度即为 \(\Theta(n\log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define MAXN 500005
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> inline void chkmax (T &a,T b){a = max (a,b);}
template <typename T> inline void chkmin (T &a,T b){a = min (a,b);}
int n,m;
struct node{
int u,v,L,R,typ;
bool operator < (const node &p)const{return L > p.L;}
};
vector <node> g[MAXN][2];
priority_queue <node> q;
int f[MAXN][2];
void addedge (int u,int v,int l,int r){
int opt = l & 1;
if (f[u][opt] >= l){//这样这条边是可走的，而且在l一定可以走，因为我们是按L加入的
if (v == n){write (l + 1),putchar ('\n');exit (0);}
if (f[v][opt ^ 1] <= r + 1){
f[v][opt ^ 1] = r + 1;
for (node it : g[v][opt ^ 1]) q.push (node{it.u,it.v,l + 1,it.R,0});
g[v][opt ^ 1].clear ();
}
}
else g[u][opt].push_back (node{u,v,l,r,0});//否则就不能走，得等下次更新
}
signed main(){
read (n,m);
if (n == 1) return puts ("0") & 0;
for (Int i = 1,u,v,L,R;i <= m;++ i){
read (u,v,L,R),-- R;int opt = R - L & 1;
q.push (node{u,v,L,R - opt,1}),q.push (node{u,v,L + 1,R - (!opt),1});
}
memset (f,0xcf,sizeof (f)),f[1][0] = 0;
while (!q.empty()){
node it = q.top();q.pop ();
if (it.L > it.R) continue;
addedge (it.u,it.v,it.L,it.R);
if (it.typ) addedge (it.v,it.u,it.L,it.R);
}
puts ("-1");
return 0;
}