正題

題目鏈接:https://www.luogu.com.cn/problem/CF827F

---

題目大意

給出$n$個(gè)點(diǎn)$m$條邊的一張無(wú)向圖，每條邊只有在時(shí)刻$[l_i,r_i)$時(shí)候才能通過(guò)，且通過(guò)時(shí)間為$1$，你不能在一個(gè)點(diǎn)處停留，求$1$走到$n$的最短時(shí)間。

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

---

解題思路

如果能停留的話(huà)顯然我們可以停留等待一條邊開(kāi)啟，儲(chǔ)存最短距離肯定最優(yōu)。

但是現(xiàn)在不能停留，考慮在一條邊處反復(fù)橫跳，而這樣我們?nèi)绻ＷC最優(yōu)吧一個(gè)點(diǎn)拆成一個(gè)奇點(diǎn)和一個(gè)偶點(diǎn)，但是現(xiàn)在的問(wèn)題是我們反復(fù)橫跳的邊是可能關(guān)閉的。

考慮把邊的$l_i$從小到大排序來(lái)進(jìn)行考慮，當(dāng)我們枚舉到一條邊時(shí)$i$如果能夠到大那么下界顯然沒(méi)有問(wèn)題（也就是能夠在$l$之前到達(dá)），那么考慮上界的限制，也就是我們至少需要反復(fù)橫跳到時(shí)間$l$才能走這條邊。

設(shè)$f_i$表示目前能夠到達(dá)$i$的最晚時(shí)間，那么當(dāng)$l\le f_i$的時(shí)候可以直接走這條邊，否則我們需要等到以后再走這個(gè)點(diǎn)的$f_i\ge l$的時(shí)候就可以了，所以我們可以把這條邊先掛在$x$上然后當(dāng)我們下次有一條邊能夠走到$x$時(shí)考慮如何處理掛在$x$上的邊。

記掛在$x$上的邊為$A$，走到$x$的邊為$B$，因?yàn)槭?span id="ze8trgl8bvbq" class="katex--inline">$A$先枚舉的顯然有$A_l\le B_l$，同樣的就有$B_r\le A_l$，所以在$B$處反復(fù)橫跳一定能走$A$，所以我們可以把所有掛在$x$上的邊取下來(lái)然后把相等于能夠新走的邊加入即可。

再開(kāi)一個(gè)維護(hù)目前的邊即可。

時(shí)間復(fù)雜度：$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; }

總結(jié)

以上是生活随笔為你收集整理的CF827F-Dirty Arkady‘s Kitchen【堆】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。