題意 ：

• 在一顆樹形迷宮中，一共有n個(gè)結(jié)點(diǎn)，有k個(gè)vlad的朋友，分別在$x_1,x_2,...$結(jié)點(diǎn)。vlad從1號(hào)結(jié)點(diǎn)出發(fā)，問，在所有朋友都同時(shí)移動(dòng)的同時(shí)，vlad是否一定可以走到一個(gè)葉子結(jié)點(diǎn)（過(guò)程中不被朋友抓住）？

思路 ：

• 求的是是否一定可以，也就是不可能被抓住，走到某一個(gè)葉子結(jié)點(diǎn)的最短路徑上的每一個(gè)點(diǎn)都比任何朋友走到這個(gè)點(diǎn)快，這樣可以保證不被抓住
• 多源最短路bfs問題，從所有朋友出發(fā)，求出到達(dá)i結(jié)點(diǎn)的最短路程，再?gòu)膙lad出發(fā)，求是否存在一條到達(dá)葉子結(jié)點(diǎn)的路徑，使得路徑上每個(gè)點(diǎn)的最短路徑都比朋友的短
• 關(guān)于bfs ：如果每一次擴(kuò)展恰好對(duì)應(yīng)一步，那么當(dāng)一個(gè)狀態(tài)第一次被訪問（入隊(duì)）時(shí)，就得到了從起始狀態(tài)到達(dá)該狀態(tài)的最少步數(shù)，就直接入隊(duì)了，且每個(gè)點(diǎn)只入隊(duì)一次。
• 第二次bfs時(shí)，如果當(dāng)前這個(gè)點(diǎn)已經(jīng)比朋友走到這的最短距離大于等于了，說(shuō)明不走這個(gè)點(diǎn)，直接continue
• 如何表示葉結(jié)點(diǎn) ？ne[h[i]] == -1，注意同時(shí)還要判斷它不是起點(diǎn)1

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <unordered_set> #include <math.h> using namespace std;typedef long long ll; typedef pair<int, int> PII;#define endl '\n' #define fi first #define se second #define push_back #define rep(i, l, r) for (ll i = l; i <= r; i ++ )const int N = 2e5 + 10, M = N * 2, inf = 0x3f3f3f3f;int n, k; int h[N], ne[M], e[M], idx; int q[N]; // 從朋友出發(fā) int dist[N]; // 所有朋友到i房間的最短時(shí)間 bool st[N]; PII mq[N]; // 從vlad出發(fā)void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }void solve() {cin >> n >> k;// init!idx = 0;for (int i = 1; i <= n; i ++ ) h[i] = -1, dist[i] = inf, st[i] = false;int hh = 0, tt = -1;for (int i = 1, x; i <= k && cin >> x; i ++ ){q[ ++ tt] = x;st[x] = true;dist[x] = 0;}for (int i = 1, u, v; i <= n - 1 && cin >> u >> v; i ++ ) add(u, v), add(v, u);while (hh <= tt){int t = q[hh ++ ];for (int i = h[t]; ~i; i = ne[i]){int j = e[i];if (!st[j]) dist[j] = dist[t] + 1, q[ ++ tt] = j, st[j] = true;}}// init!!for (int i = 1; i <= n; i ++ ) st[i] = false;hh = 0, tt = 0;mq[0] = {1, 0};st[1] = true;while (hh <= tt){auto t = mq[hh ++ ];int r = t.fi, d = t.se;if (d >= dist[r]) continue;if (ne[h[r]] == -1 && r != 1 && d < dist[r]) return cout << "Yes\n", void();for (int i = h[r]; ~i; i = ne[i]){int j = e[i];if (!st[j]) mq[ ++ tt] = {j, d + 1}, st[j] = true; // 每個(gè)點(diǎn)第一次被訪問就入隊(duì)}}cout << "No\n"; }int main() {cin.tie(nullptr) -> sync_with_stdio(false);int _;cin >> _;while (_ -- )solve();return 0; }

總結(jié)

以上是生活随笔為你收集整理的Escape The Maze (easy version) 多源最短路，bfs（1700）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。