CodeForces-1321D Navigation System

传送门：CodeForces-1321D

题目描述

给出一个由 $n$ 个点和 $m$ 条边组成的有向图，现在有一个人，他有一条固定的路线，这个题目中有一个导航，当到达任意一个点时，导航都会给出一条通往终点的最短路，但是这个人固定的路线并不一定每次都是最短路，导航最初会给出一条最短路，如果这个人不按照最短路行走的话，那么导航需要“重构”最短路，题目问“重构”的最小次数和最大次数

思路分析

先建反边，求出每个点到终点的最短路，然后题目给了$k-1$条边，对于每一条边$u->v$，判断一下：

• 如果这条边不在最短路上面$(dis[u]!=dis[v]+1)$说明肯定要重构，所以 $min++$，$max++$
• 否则如果$u$与其他节点$nv$存在一条边，且$(dis[u]=dis[nv]+1)$,说明可以重构，$max++$

样例输入

6 9
1 5
5 4
1 2
2 3
3 4
4 1
2 6
6 4
4 2
4
1 2 3 4

样例输出

1 2

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;

int n, m, a[N], dis[N], vis[N];
vector<int>e[N], re[N];

void spfa(int s) {
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
        vis[i] = 0;
    }
    queue<int>q;
    vis[s] = 1;
    dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (auto v : re[u]) {
            if (dis[v] > dis[u] + 1) {
                dis[v] = dis[u] + 1;
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif

    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        re[v].push_back(u);
    }
    int k;
    cin >> k;
    for (int i = 1; i <= k; i++)
        cin >> a[i];
    spfa(a[k]);
    int mi = 0, ma = 0;
    int u = a[1];
    for (int i = 2; i <= k; i++) {
        int v = a[i];
        if (dis[u] != dis[v] + 1) {
            mi++;
            ma++;
        } else {
            for (auto nv : e[u]) {
                if (nv == v)continue;
                if (dis[u] == dis[nv] + 1) {
                    ma++;
                    break;
                }
            }
        }
        u = v;
    }
    cout << mi << " " << ma << endl;




    return 0;
}