正题
题目链接:https://www.luogu.com.cn/problem/CF827F
题目大意
给出\(n\)个点\(m\)条边的一张无向图，每条边只有在时刻\([l_i,r_i)\)时候才能通过，且通过时间为\(1\)，你不能在一个点处停留，求\(1\)走到\(n\)的最短时间。
\(1\leq n,m\leq 5\times 10^5\)
解题思路
如果能停留的话显然我们可以停留等待一条边开启，储存最短距离肯定最优。
但是现在不能停留，考虑在一条边处反复横跳，而这样我们如果要保证最优吧一个点拆成一个奇点和一个偶点，但是现在的问题是我们反复横跳的边是可能关闭的。
考虑把边的\(l_i\)从小到大排序来进行考虑，当我们枚举到一条边时\(i\)如果能够到大那么下界显然没有问题（也就是能够在\(l\)之前到达），那么考虑上界的限制，也就是我们至少需要反复横跳到时间\(l\)才能走这条边。
设\(f_i\)表示目前能够到达\(i\)的最晚时间，那么当\(l\leq f_i\)的时候可以直接走这条边，否则我们需要等到以后再走这个点的\(f_i\geq l\)的时候就可以了，所以我们可以把这条边先挂在\(x\)上然后当我们下次有一条边能够走到\(x\)时考虑如何处理挂在\(x\)上的边。
记挂在\(x\)上的边为\(A\)，走到\(x\)的边为\(B\)，因为是\(A\)先枚举的显然有\(A_l\leq B_l\)，同样的就有\(B_r\leq A_l\)，所以在\(B\)处反复横跳一定能走\(A\)，所以我们可以把所有挂在\(x\)上的边取下来然后把相等于能够新走的边加入即可。
再开一个维护目前的边即可。
时间复杂度：\(O(m\log m)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const ll N=1e6+10;
struct node{
ll x,y,l,r;
};
ll n,m,f[N];
bool operator<(node x,node y)
{return x.l>y.l;}
priority_queue<node> q;
vector<node> e[N];
signed main()
{
scanf("%lld%lld",&n,&m);
if(n==1)return puts("0")&0;
for(ll i=1;i<=m;i++){
ll x,y,l,r;
scanf("%lld%lld%lld%lld",&x,&y,&l,&r);r--;
q.push((node){x,y+n,l+(l&1),r-(r&1)});
q.push((node){y,x+n,l+(l&1),r-(r&1)});
q.push((node){x+n,y,l+!(l&1),r-!(r&1)});
q.push((node){y+n,x,l+!(l&1),r-!(r&1)});
}
memset(f,0xcf,sizeof(f));f[1]=0;
while(!q.empty()){
node x=q.top();q.pop();
if(x.l>x.r)continue;
if(x.l>f[x.x]){e[x.x].push_back(x);continue;}
if(x.y==n||x.y==2*n)return printf("%lld\n",x.l+1)&0;
f[x.y]=max(f[x.y],x.r+1);
for(ll i=0;i<e[x.y].size();i++){
node y=e[x.y][i];
y.l=x.l+1;q.push(y);
}
e[x.y].clear();
}
puts("-1");
return 0;
}