CF827F-Dirty Arkady‘s Kitchen【堆】

CF827F-Dirty Arkady‘s Kitchen【堆】 正题

题目链接:https://www.luogu.com.cn/problem/CF827F

---

题目大意

给出 n n n个点 m m m条边的一张无向图，每条边只有在时刻 [ l i , r i ) [l_i,r_i) [li​,ri​)时候才能通过，且通过时间为 1 1 1，你不能在一个点处停留，求 1 1 1走到 n n n的最短时间。

1 ≤ n , m ≤ 5 × 1 0 5 1leq n,mleq 5times 10^5 1≤n,m≤5×105

---

解题思路

如果能停留的话显然我们可以停留等待一条边开启，储存最短距离肯定最优。

但是现在不能停留，考虑在一条边处反复横跳，而这样我们如果要保证最优吧一个点拆成一个奇点和一个偶点，但是现在的问题是我们反复横跳的边是可能关闭的。

考虑把边的 l i l_i li​从小到大排序来进行考虑，当我们枚举到一条边时 i i i如果能够到大那么下界显然没有问题（也就是能够在 l l l之前到达），那么考虑上界的限制，也就是我们至少需要反复横跳到时间 l l l才能走这条边。

设 f i f_i fi​表示目前能够到达 i i i的最晚时间，那么当 l ≤ f i lleq f_i l≤fi​的时候可以直接走这条边，否则我们需要等到以后再走这个点的 f i ≥ l f_igeq l fi​≥l的时候就可以了，所以我们可以把这条边先挂在 x x x上然后当我们下次有一条边能够走到 x x x时考虑如何处理挂在 x x x上的边。

记挂在 x x x上的边为 A A A，走到 x x x的边为 B B B，因为是 A A A先枚举的显然有 A l ≤ B l A_lleq B_l Al​≤Bl​，同样的就有 B r ≤ A l B_rleq A_l Br​≤Al​，所以在 B B B处反复横跳一定能走 A A A，所以我们可以把所有挂在 x x x上的边取下来然后把相等于能够新走的边加入即可。

再开一个维护目前的边即可。

时间复杂度： O ( m log ⁡ m ) O(mlog m) O(mlogm)

---

code

#include
#include
#include
#include
#include
#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 q;
vector 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("%lldn",x.l+1)&0;
		f[x.y]=max(f[x.y],x.r+1);
		for(ll i=0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5634578.html