B. Navigation System【CF 1320】

传送门

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

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

  1 #include <iostream>

  2 #include <algorithm>

  3 #include <cstdio>

  4 #include <cstring>

  5 #include <queue>

  6 #include <string>

  7 #include <map>

  8 #include <set>

  9 #include <vector>

 10 #define LL long long

 11 using namespace std;

 12

 13 const int N = 2e5 + 10;

 14 const int INF = 1e9;

 15 vector<int > E[2][N];

 16 vector<int > lev[N];

 17 int d[2][N], v[N];

 18 int n, m;

 19

 20 void bfs(int s, int t, int pos)

 21 {

 22     for(int i = 1; i <= n; ++i) d[pos][i] = 1e9;

 23     d[pos][s] = 1;

 24     queue<int > que;

 25     que.push(s);

 26

 27     while(!que.empty()) {

 28         int now = que.front();

 29         que.pop();

 30

 31         for(auto to : E[pos][now]) {

 32             if(d[pos][to] > d[pos][now] + 1) {

 33                 d[pos][to] = d[pos][now] + 1;

 34                 que.push(to);

 35             }

 36         }

 37     }

 38 }

 39

 40 void solve()

 41 {

 42     scanf("%d%d", &n, &m);

 43     for(int i = 0; i < m; ++i) {

 44         int x, y;

 45         scanf("%d%d", &x, &y);

 46         E[0][x].push_back(y);

 47         E[1][y].push_back(x);///反向边

 48     }

 49

 50     int steps;

 51     scanf("%d", &steps);

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

 53

 54     bfs(v[1], v[steps], 0);

 55     bfs(v[steps], v[1], 1);///反向最短路

 56 /*

 57     for(int i = 1; i <= n; ++i) {

 58         printf("d[%d] = %d\n", i, d[0][i]);

 59     }

 60     for(int i = 1; i <= n; ++i) {

 61         printf("d[%d] = %d\n", i, d[1][i]);

 62     }

 63

 64

 65     for(int i = 1; i <= n; ++i) {

 66         if(d[1][i] == INF) continue;

 67         lev[ d[1][i] ].push_back(i);

 68     }

 69 */

 70     int Min, Max;

 71     Min = Max = 0;

 72     for(int i = 1; i < steps; ++i) {

 73         int now = v[i];

 74         int to = v[i + 1];

 75         int to_d = d[1][to];

 76         int flag = 0;

 77         int tot = 0;

 78         for(auto other : E[0][now]) {

 79             if(to == other) continue;

 80             if(to_d > d[1][other]) { ///不是最短路

 81                 Max++;

 82                 Min++;

 83                 flag = 1;

 84                 break;

 85             } else if(to_d == d[1][other]) { tot++; }

 86         }

 87

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

 89     }

 90

 91     ///printf("Min = %d Max = %d\n", Min, Max);

 92     printf("%d %d\n", Min, Max);

 93 }

 94

 95 int main()

 96 {

 97     solve();

 98

 99     return 0;

100 }

巴特西

B. Navigation System【CF 1320】

最新文章

热门文章