题目

题目链接：https://codeforces.com/contest/827/problem/F
给定一张无向图，每条边在时间 \([l_i,r_i)\) 才能通过，通过花费 \(1\) 的时间。你不能在原地停留。
你在时刻 \(0\) 从 \(1\) 号点，求最快何时能到达 \(n\) 号点。
无法到达或*停留，输出 -1。
\(n,m\leq 5\times 10^5\)。

思路

因为可以在一条边上反复横跳，所以如果把每一个点拆成奇点和偶点的话，能到达的时间可以看作是若干个区间的交。
因为每一个点都拆成了两个点，那么原来的一条无向边就能拆成 \(4\) 条有向边。把有向边按照 \(l\) 排序。
设 \(f[x]\) 表示可以到达点 \(x\) 的最晚时间。那么对于一条边 \((u,v,l,r)\)，可以在第 \(l+1\) 时刻到达 \(v\) 当且仅当现在 \(f[u]\geq l\) 的。如果不能直接到达，我们就把这一条边扔进 \(u\) 的一个 vector 内。
如果可以在 \(l+1\) 时刻到达，我们就把 \(f[v]\) 更新为 \(\max(f[v],r+1)\)，然后把在 \(v\) vector 内的边都处理掉。因为此时这些边一定都可以走。注意这些边的 \(l\) 都需要更改为 \(l+1\)。
时间复杂度 \(O(n\log n)\)。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1000010;
int n,m,f[N];

struct node
{
	int u,v,l,r;
	
	friend bool operator <(node x,node y)
	{
		return x.l>y.l;
	}
};
vector<node> e[N];
priority_queue<node> q;

int main()
{
	scanf("%d%d",&n,&m);
	if (n==1) return printf("0"),0;
	for (int i=1,u,v,l,r;i<=m;i++)
	{
		scanf("%d%d%d%d",&u,&v,&l,&r);
		r--;
		q.push((node){u,v+n,l+(l&1),r-(r&1)});
		q.push((node){v,u+n,l+(l&1),r-(r&1)});
		q.push((node){u+n,v,l+!(l&1),r-!(r&1)});
		q.push((node){v+n,u,l+!(l&1),r-!(r&1)});
	}
	memset(f,-1,sizeof(f));
	f[1]=0;
	while (q.size())
	{
		node u=q.top(); q.pop();
		if (u.l>u.r) continue;
		if (u.l>f[u.u]) { e[u.u].push_back(u); continue; }
		if (u.v==n || u.v==2*n) return printf("%d",u.l+1),0;
		f[u.v]=max(f[u.v],u.r+1);
		for (int i=0;i<(int)e[u.v].size();i++)
		{
			node v=e[u.v][i];
			v.l=u.l+1; q.push(v);
		}
		e[u.v].clear();
	}
	cout<<"-1";
	return 0;
}