傳送門
題目：簡單理解就是，我們需要開車從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 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/238415.html
標籤：其他