正题

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

---

题目大意

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

$1\le n,m\le 5\times 10^5$

---

解题思路

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

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

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

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

记挂在$x$上的边为$A$，走到$x$的边为$B$，因为是$A$先枚举的显然有$A_l\le B_l$，同样的就有$B_r\le 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; }

总结

以上是生活随笔为你收集整理的CF827F-Dirty Arkady‘s Kitchen【堆】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。