Codeforces Round 625 D. Navigation System


题意简述

缺德地图持续为您导航
给定一个$n$个点$m$个单向边的图,以及$p_1,p_2,\cdots,p_k$这么一段指定路径,$p_1$是起点,$p_k$是终点,每到一个点都会给出当前到终点的最短距离,所以到下一个点时,可能上次的最短路就不满足现在的情况,就需要重建,当然最短路也有多条,所以选择不同的最短路对后续也有影响,不同的路重建次数也不一样,要求求出最小重建次数和最大重建次数

题解

这题真的不难,但是当时怎么就,可能还是节奏不行,看看过题人数有时候都没细想脑子里稍微过一过感觉有点烦就没写,以后还是得多想想啊
我们首先反向建边然后处理出最短路,并且统计一下最短路数,就是最短路计数,看看在这个点有多少最短路可以到达,之后我们for一遍$p$数组,假如$dis[p_i-1]-1!=dis[p_i]$的话那么这两个就一定不在一个最短路上,因为最短路径上的每一点都是最短路,所以我们就可以把最小重建和最大重建都加1
当他们在最短路径上的时候,我们可以看看$cnt[p_i]$即到$p_i$的最短路径条数,假如大于1那么肯定不止$p_i$,所以就可以挑一个其他点这样就可以多一次重建,那么最大重建就加1
最后输出答案即可

AC代码

const int inf=0x3f3f3f3f;
const int maxn=200050;
int n,m,k;
int p[maxn];
int head[maxn],num;
int d[maxn],vis[maxn],cnt[maxn];
struct node{
    int v,nex;
}e[maxn];
void add(int u,int v)
{
    e[++num].nex=head[u];
    e[num].v=v;
    head[u]=num;
}
void dij(int s)
{
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    priority_queue<PII,vector<PII>,greater<PII> > q;
    q.push(make_pair(0,s));
    d[s]=0;
    while(!q.empty())
    {
        int u=q.top().second;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].nex)
        {
            int v=e[i].v;
            if(d[v]>d[u]+1)
            {
                d[v]=d[u]+1;
                cnt[v]=1;
                q.push(make_pair(d[v],v));
            }
            else if(d[v]==d[u]+1) cnt[v]++;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;read(x),read(y);
        add(y,x);
    }
    cin>>k;
    for(int i=1;i<=k;i++) read(p[i]);
    int ans1,ans2;
    ans1=ans2=0;
    dij(p[k]);
    for(int i=2;i<=k;i++)
    {
        if(d[p[i-1]]-1!=d[p[i]]) ans1++,ans2++;
        else if(cnt[p[i-1]]>1) ans2++;
    }
    cout<<ans1<<" "<<ans2<<endl;
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
  目录