B. Navigation System【CF 1320】

传送门

题目：简单理解就是，我们需要开车从s点到t点。车上有一个导航，如果当前点为x，则导航会自动为你提供一条从x到t的最短的路线（如果有多条，则随机选一条），每走到下一个点则会实时更新最短路线，当然，如果你按着之前提供的路线走到下一个点，则路线不会更新。题目提供一条确定的路线，如果按着提供的路线走，问导航最多会更新几次，最少会更新几次。

思路：切入点很简单，我们按着路线一个个点走，需要确定走到该点的时候，该点是不是包含在最短路线中，如果包含，是不是唯一的，如果唯一，不更新，否则更新；如果不包含，也会更新。因为我们需要确定从每个点出发走到t的最短距离从而确定导航需不需要更新，所以我们需要反向建边，然后跑一个最短路，求得t到其他点的最短距离，也就得到其他点到t的最短距离。这样，我们只需要枚举路线的当前点，得到路线中下一个点到t的距离，然后按照“红色”更新答案即可，有一种“走一步看一步”的感觉。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <vector>
#define LL long long
using namespace std;

const int N = 2e5 + 10;
const int INF = 1e9;
vector<int > E[2][N];
vector<int > lev[N];
int d[2][N], v[N];
int n, m;

void bfs(int s, int t, int pos)
{
    for(int i = 1; i <= n; ++i) d[pos][i] = 1e9;
    d[pos][s] = 1;
    queue<int > que;
    que.push(s);

    while(!que.empty()) {
        int now = que.front();
        que.pop();

        for(auto to : E[pos][now]) {
            if(d[pos][to] > d[pos][now] + 1) {
                d[pos][to] = d[pos][now] + 1;
                que.push(to);
            }
        }
    }
}

void solve()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        E[0][x].push_back(y); 
        E[1][y].push_back(x);///反向边
    }

    int steps;
    scanf("%d", &steps);
    for(int i = 1; i <= steps; ++i) { scanf("%d", v + i); }

    bfs(v[1], v[steps], 0);
    bfs(v[steps], v[1], 1);///反向最短路
/*
    for(int i = 1; i <= n; ++i) {
        printf("d[%d] = %d
", i, d[0][i]);
    }
    for(int i = 1; i <= n; ++i) {
        printf("d[%d] = %d
", i, d[1][i]);
    }


    for(int i = 1; i <= n; ++i) {
        if(d[1][i] == INF) continue;
        lev[ d[1][i] ].push_back(i);
    }
*/
    int Min, Max;
    Min = Max = 0;
    for(int i = 1; i < steps; ++i) {
        int now = v[i];
        int to = v[i + 1];
        int to_d = d[1][to];
        int flag = 0;
        int tot = 0;
        for(auto other : E[0][now]) {
            if(to == other) continue;
            if(to_d > d[1][other]) { ///不是最短路
                Max++;
                Min++;
                flag = 1;
                break;
            } else if(to_d == d[1][other]) { tot++; } 
        }

        if(!flag && tot) { Max++; } ///不是唯一的最短路
    }

    ///printf("Min = %d Max = %d
", Min, Max);
    printf("%d %d
", Min, Max);
}

int main()
{
    solve();

    return 0;
}