题解：CF827F Dirty Arkady's Kitchen

· · 题解

CF827F Dirty Arkady's Kitchen

由于有开放时间和不能停留的限制，此时从最快到达时间转移就没有正确性了，因为可能到了这里走不了。不过注意到，由于是无向图，到了 u 之后可以用入边反复横跳，即 p\leftrightarrow u 之间来回跳，那么每次可以耗掉 2 单位时间，因此如果 x 时刻可以到达，那么 x+2k 时刻也可以到达，换言之，可以到达时间分奇偶考虑。将每个点拆成奇点和偶点，因此两点之间也会建立奇边和偶边，每条边 (u,v,l,r)，表示从 u\to v 的边在 [l,r] 时刻有效。

考虑此时出现时间的限制，先将所有边按照 l_i 排序依次拓展，这样子就可以保证走来的边满足下界的限制。然后记录一个 f_{u,0/1} 分别表示到达当前奇点偶点的最晚时间，那么考虑一条边 (u,v,l,r)，由于 f_u 是最晚时间，此时 u 不能在来时路继续乱搞了，只能走下去。如果 f_u\ge l，说明 u 能且只能在 l 时刻到达这里并通过这条边，在 (l+1) 时刻走到 v，然后在这条边上乱搞，并最晚于 (r+1) 时刻走到 v，因此更新 f_v\leftarrow \max(f_v,r+1)。否则说明 u 在当前这些边的更新下还不足以走这条边，但是在后面增加边时可能就可以走了，因此在 u 处挂上 v，在后面 u 被打通时就把所有的 (u,v) 边加入更新。

:::info[代码]

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define psb push_back
#define SZ(vec) ((int)vec.size())
#include <queue>

using namespace std;

const int N=500010;
int n,m;
struct Node
{
    int u,v,l,r,dir;
    bool operator < (const Node &o) const { return l>o.l; }
};
priority_queue<Node> q;
int f[N][2];
vector<Node> buc[N][2];

void spread(int u,int v,int l,int r)
{
    bool op=(l&1);
    if (f[u][op]>=l)
    {
        if (v==n) 
        {
            cout << l+1 << "\n";
            exit(0);
        }
        if (f[v][!op]<=r+1)
        {
            f[v][!op]=r+1;
            for (Node t : buc[v][!op]) q.push({t.u,t.v,l+1,t.r,1});
            buc[v][!op].clear();
        }
    }
    else buc[u][op].psb({u,v,l,r});
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> n >> m;
    if (n==1)
    {
        puts("0");
        return 0;
    }
    for (int i=1;i<=m;i++)
    {
        int u,v,l,r;
        cin >> u >> v >> l >> r; r--;
        bool op=((l&1)==(r&1));
        q.push({u,v,l,r-(!op),0});
        q.push({u,v,l+1,r-op,0});
    }
    memset(f,0xcf,sizeof(f)); 
    f[1][0]=0;
    while (q.size())
    {
        auto [u,v,l,r,dir]=q.top(); q.pop();
        if (l>r) continue;
        spread(u,v,l,r);
        if (!dir) spread(v,u,l,r);
    }
    puts("-1");

    return 0; 
}

:::