• 周六. 8月 20th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

AcWing 3772. 更新线路(BFS)

admin

11月 28, 2021

小白刷题中
做一道BFS的题,参考https://www.acwing.com/video/3312/

题意

给定一条路径,小明沿着路径走。导航软件会给小明推荐最短路径。
首先,在点 s 处,导航软件会找到并显示出一条从点 s 到点 t 的最短路径。
如果小明的行进线路恰好与软件推荐线路一致,则软件推荐线路将不会发生任何改变。
但是,如果小明在某一点处,行进线路与软件推荐线路发生了分歧,例如,软件推荐前往点 v,小明却前往了点 w。
那么,在他到达点 w 后,软件就会实时更新推荐线路,即找到并显示出一条从点 w 到点 t 的最短路径。
导航软件会一直工作到小明到达点 t 为止,在这一过程中,软件的提供线路可能会经过若干次更新。
由于软件在推荐最短路径时具有随机性,所以在整个行进过程中,软件更新推荐线路的次数并不确定。
现在,给定有向图和行进路线,请你求出软件更新推荐线路的最小可能次数和最大可能次数。

输入输出

输入:第一行包含两个整数 n 和 m。
接下来 m 行,每行包含两个整数 u,v,表示存在一条从点 u 到点 v 的有向边。
随后一行包含一个整数 k。
最后一行包含 k 个整数 p1,p2,…,pk。
输出:一行,空格隔开的两个整数,表示软件更新推荐路线的最小可能次数和最大可能次数。

思路

小明走的路径中,如果a->b不在一条最短路径中,那么最小可能次数和最大可能次数都要加一;
如果a->b在一条最短路径中,分情况讨论:1.a只能走b,导航就不需要更新;2.a还能走别的最短路径,那么最大推荐次数加一,最小推荐次数不变。
用bfs来更新给个点到给出路径终点的最短路径,以给出路径的终点作为bfs的起点,建立反向边,更新每个点的最短路径。同时还可以记录每个点有多少条出边。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;
int tot;
int head[N],ver[N],nxt[N];  //建邻接表需要的数组
int dist[N],cnt[N];
int path[N];    //路径
int q[N];   //队列

void add(int u, int v)  // 添加一条边u->v
{
    ver[++tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
}

void bfs(int start){    //计算每个点到终点的最短路径长度,同时记录下每个点在最短路上出边的数量
    int hh=0, tt=0; //hh为遍历队列的指针,tt为队尾指针
    memset(dist, 0x3f, sizeof dist);    //初始化为无穷大
    q[0] = start;   //先将起点入队列
    dist[start] = 0;
    while(hh <= tt){
        int u = q[hh++];
        for(int i = head[u]; i;i = nxt[i]){ //遍历u的所有邻接点
            int v = ver[i];
            if(dist[v] > dist[u] + 1){
                dist[v] = dist[u] + 1;
                cnt[v]++;
                q[++tt] = v;
            }
            else if(dist[v] == dist[u] + 1){
                cnt[v]++;
            }
        }
    }
}

int main()
{
    int n,m,k;
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ){
        int u,v;
        cin >> u >> v;
        add(v,u);   //建立反向边,因为要计算每个点到终点的最短路
    }
    cin >> k;
    for (int i = 1; i <= k; i ++ ) cin >> path[i];
    bfs(path[k]);
    int minc=0,maxc=0;
    for(int i = 1;i < k;i++){
        int u=path[i],v=path[i+1];  //遍历给出路径上的点
        if(dist[u] < dist[v] + 1){
            minc++;maxc++;
        }
        else if(dist[u] == dist[v] + 1){
            if(cnt[u] > 1) maxc++;
        }
    }
    cout << minc << " " << maxc;
    return 0;
}

作者:inss!w!
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!

发表回复

您的电子邮箱地址不会被公开。