nearest_shops_3303.cpp (1235B)
1 #include <algorithm> 2 #include <iostream> 3 #include <queue> 4 #include <tuple> 5 #include <vector> 6 7 // The difficult part is finding for every city with an anime shop the 8 // closest other city with a shop. We do this via a "double BFS", where 9 // we reach each node twice from two different sources. 10 11 struct V { int v1; int s1; int v2; int s2; }; 12 13 int main() { 14 constexpr int max{99999999}; 15 int n, m, k, x, y; 16 std::queue<std::tuple<int, int, int>> q; 17 std::cin >> n >> m >> k; 18 std::vector<V> v(n, {max, -1, max, -1}); 19 for (int i = 0; i < k; i++) { 20 std::cin >> x; 21 v[x-1] = {0, x-1, max, -1}; 22 q.push({x-1, 0, x-1}); 23 } 24 std::vector<std::vector<int>> a(n); 25 for (int i = 0; i < m; i++) { 26 std::cin >> x >> y; 27 a[x-1].push_back(y-1); 28 a[y-1].push_back(x-1); 29 } 30 31 while (!q.empty()) { 32 auto [u, w, s] = q.front(); 33 q.pop(); 34 for (auto z : a[u]) { 35 if (z == s) continue; 36 auto& [v1, s1, v2, s2] = v[z]; 37 if (v1 > w+1) { 38 v1 = w+1; 39 s1 = s; 40 q.push({z, w+1, s}); 41 } else if (s1 != s && v2 > w+1) { 42 v2 = w+1; 43 s2 = s; 44 q.push({z, w+1, s}); 45 } 46 } 47 } 48 49 for (int i = 0; i < n; i++) { 50 auto [x, s, y, _] = v[i]; 51 auto w = s == i ? y : x; 52 std::cout << (w == max ? -1 : w) << " "; 53 } 54 std::cout << "\n"; 55 }