CF1320B Navigation System

发表于2020-09-03更新于2023-09-17字数统计646阅读时长5分作者Shane

题目链接

Solution

Rebuild 最少：若有多条最短路，让每次导航恰好取和工作路径部分重合或完全重合的最短路。如果当前节点经工作路径到终点的距离大于到该点的最短路，且该节点到终点的最短路、工作路径没有公共前缀，一定会 Rebuild，有交集就不 Rebuild; 如果工作路径和最短路完全重合，则不会再 Rebuild，beak即可。

Rebuild 最多：若有多条最短路，让每次导航优尽量取在工作路径外的最短路。如果当前节点经工作路径到终点的距离大于到该点的最短路，且该节点到终点的最短路、工作路径没有公共前缀，一定 Rebuild ; 若当前节点经工作路径到终点的距离等于到该点的最短路，且有多条最短路优先取工作路径以外的, 若仅有一条最短路，即只能取在工作路径上的，则不会再 Rebuild，beak即可。

Code

Navigation System
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 2e5 + 5;

int n, m, c;
vector<int> G[MAXN];
array<int, MAXN> dis, inq, id, onChain, outChain, chain, chainDis;

inline void spfa(int st) {
    fill(dis.begin(), dis.begin() + n + 1, 1e9);
    deque<int> q;
    q.push_back(st), dis[st] = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop_front(), inq[cur] = false;
        for (auto& to : G[cur]) {
            if (dis[to] > dis[cur] + 1) {
                dis[to] = dis[cur] + 1;
                onChain[to] = outChain[to] = 0;
                if (id[to] && id[cur] && id[cur] - 1 == id[to]) onChain[to] = 1;
                else outChain[to] = 1;
                if (!inq[to]) { //slf
                    if (q.empty() || dis[to] < dis[q.front()]) q.push_front(to);
                    else q.push_back(to);
                    inq[to] = true;
                }
            } else if (dis[to] == dis[cur] + 1) { //多条最短路
                if (id[to] && id[cur] && id[cur] - 1 == id[to]) onChain[to] = 1;
                else outChain[to] = 1; //不在链上
            }
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) cin >> u >> v, G[v].push_back(u);
    cin >> c;
    for (int i = 1; i <= c; i++) cin >> chain[i], id[chain[i]] = i;
    spfa(chain[c]); //处理最短路
    for (int i = c - 1; i >= 1; i--) //处理工作路径到终点的距离
        chainDis[chain[i]] = chainDis[chain[i + 1]] + 1;
    int min = 0, max = 0;
    for (int i = 1; i < c; i++) {
        if (chainDis[chain[i]] > dis[chain[i]]) {
            if (!onChain[chain[i]]) min++;
        } else break;
    }
    for (int i = 1; i < c; i++) {
        if (chainDis[chain[i]] > dis[chain[i]]) {
            if (outChain[chain[i]]) max++;
        } else {
            if (outChain[chain[i]]) max++; //有多条最短路
            else break;
        }
    }
    cout << min << " " << max << endl;
    return 0;
}