题解 CF685E【Travelling Through the Snow Queen's Kingdom】

· · 题解

CF685E Travelling Through the Snow Queen's Kingdom解题报告：

更好的阅读体验

题意

给定 n 个点 m 条边的无向图，第 i 条边能且仅能在i时刻经过，经过每一条边需要 1 的时间， q 次询问 l 时刻在 s 结点出发，能否在 r 时刻前到达结点 t 。（2\leqslant n\leqslant 1000,1\leqslant m,q\leqslant 2\times 10^5）

分析

这种区间限制一看就要离线搞，考虑把每个询问挂在某个时间点上扫一遍，维护一个限制之后再用 dp 求出最值看看能不能满足另一个限制。

具体的，我们发现 O(n^2) 的空间复杂度和 O(nm) 的时间复杂度都可以接受，所以考虑设 dis_{a,b} 表示在当前的图内 a 到达 b 的最小时间点，然后每次加边时维护 dis 。

将边按编号从大到小加入，每次类似 Floyd 地更新 dis_{a,b} ，不难发现每次这样加入一定可以满足走完编号小的才能走编号大的边。

最后询问挂在 l 上，然后直接查一下就可以了。

时间复杂度： O(nm+q) 。

代码

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
const int maxn=1005,maxm=200005,maxq=200005;
int n,m,q;
int x[maxm],y[maxm],R[maxq],S[maxq],T[maxq],ans[maxq],dis[maxn][maxn];
vector<int>v[maxm];
int main(){
    memset(dis,0x3f,sizeof(dis));
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=q;i++){
        int l;
        scanf("%d%d%d%d",&l,&R[i],&S[i],&T[i]);
        v[l].push_back(i);
    }
    for(int i=m;i>=1;i--){
        dis[x[i]][y[i]]=dis[y[i]][x[i]]=i;
        for(int j=1;j<=n;j++){
            dis[x[i]][j]=min(dis[x[i]][j],dis[y[i]][j]);
            dis[y[i]][j]=min(dis[y[i]][j],dis[x[i]][j]);
        }
        for(int j=0;j<v[i].size();j++){
            int k=v[i][j];
            ans[k]=(dis[S[k]][T[k]]<=R[k]);
        }
    }
    for(int i=1;i<=q;i++)
        puts(ans[i]==0? "No":"Yes");
    return 0;
}

整场比赛的题解