CF1887B Time Travel

luogu 的题面很好，此处不过多描述题面。

思路

观察题目，很容易想到最短路，推荐使用 Dijkstra 进行求解。
根据 dij 的定义，我们设

dist_{i}

表示到达第

i

的点所需的最小时间。
继续，按照 dij 的过程，接下来是访问每一个点并进行松弛。从

u

开始，每一次有两种选择：

等待 1 秒。
沿着一条连通 $u$ 和 $v$ 的路径移动到 $v$ 。

遍历每一条可以经过的路径，这一定是不正确的，时间复杂度会直接飞起来，考虑优化。
首先，贪心的考虑，在走每一条可以通过的路径时，一定是最近的这条路径可以通过的时间点（少等一定是更优的），又因为时间一定是单调上升的，自然想到二分。
所以我们每遍历到一条路径就二分出这条路径距离目前的时间最近的开启时间点

t

，然后即可用

t

来进行松弛：

\min(dist_v,t) \to dist_v

，而为了便于二分，我们将每一个边集可以通行的全部时间记录下来，这道题就解决了。
时间复杂度

O(m(\log n+\log k))

，AC 代码：

CPP

#include<bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define pii pair<int,int>
typedef long long ll;
inline int read()
{
    int x=0,t=1;
    char c=getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-')
            t=-1;
        c=getchar();
    }
    while(c>='0' && c<='9')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*t;
}
inline void write(int x)
{
    if(x<0)
    {
        x=-x;
        putchar('-');
    }
    if(x>=10) write(x/10);
    putchar(x%10^48);
    return ;
}
inline void write_L(int x)
{
    write(x);
    putchar('\n');
}
const int inf=0x3f3f3f3f;
const int N=2e5+10;
int n,t,k;
struct node
{
    int v,w;
    bool operator <(const node& a) const
    {
        return a.w<w;
    }
};
vector<node> e[N];
vector<int> g[N];
int dist[N];
bool vis[N];
void dij(int s)
{
    priority_queue<node> q;
    memset(dist,0x3f,sizeof(dist));
    dist[s]=1;
    q.push({s,1});
    while(!q.empty())
    {
        int u=q.top().v,id=q.top().w;
        q.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(auto i:e[u])
        {
            int v=i.v,w=i.w;
            int p=lower_bound(g[w].begin(),g[w].end(),id)-g[w].begin();
            if(p<g[w].size() && dist[v]>g[w][p]+1)
            {
                dist[v]=g[w][p]+1;
                q.push({v,dist[v]});
            }
        }
    }
}
int main ()
{
    n=read(),t=read();
    for(int i=1;i<=t;i++)
    {
        int m=read();
        for(int j=1;j<=m;j++)
        {
            int u=read(),v=read();
            e[u].push_back({v,i});
            e[v].push_back({u,i});
        }
    }
    k=read();
    for(int i=1;i<=k;i++)
    {
        int a=read();
        g[a].push_back(i);
    }
    dij(1);
    if(dist[n]>=inf)
        write_L(-1);
    else
        write_L(dist[n]-1);
    return 0;
}

题解：CF1887B Time Travel

文章操作

CF1887B Time Travel

思路

相关推荐

评论

题解：CF1887B Time Travel