Multi-Source BFS

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Reads an undirected unweighted graph and a set of sources.
5
// Outputs the distance from each vertex to its nearest source (or -1 if unreachable).
6
// Input format:
7
// n m
8
// m lines: u v  (1-based vertices)
9
// k
10
// k lines: s_i  (1-based sources)
11
// Example:
12
// 6 6
13
// 1 2
14
// 2 3
15
// 3 4
16
// 4 5
17
// 5 6
18
// 1 6
19
// 2
20
// 1
21
// 5
22
int main() {
23
    ios::sync_with_stdio(false);
24
    cin.tie(nullptr);
25
26
    int n, m; 
27
    if (!(cin >> n >> m)) return 0;
28
    vector<vector<int>> adj(n);
29
    for (int i = 0; i < m; ++i) {
30
        int u, v; cin >> u >> v; --u; --v;
31
        adj[u].push_back(v);
32
        adj[v].push_back(u);
33
    }
34
    int k; cin >> k;
35
    vector<int> src(k);
36
    for (int i = 0; i < k; ++i) { cin >> src[i]; --src[i]; }
37
38
    const int INF = 1e9;
39
    vector<int> dist(n, INF);
40
    queue<int> q;
41
42
    // Initialize all sources with distance 0
43
    for (int s : src) {
44
        if (dist[s] == 0) continue; // avoid duplicates
45
        dist[s] = 0;
46
        q.push(s);
47
    }
48
49
    // Standard BFS expansion
50
    while (!q.empty()) {
51
        int u = q.front(); q.pop();
52
        for (int v : adj[u]) {
53
            if (dist[v] == INF) {
54
                dist[v] = dist[u] + 1;
55
                q.push(v);
56
            }
57
        }
58
    }
59
60
    // Print distances (use -1 for unreachable)
61
    for (int v = 0; v < n; ++v) {
62
        cout << (dist[v] == INF ? -1 : dist[v]) << (v + 1 == n ? '\n' : ' ');
63
    }
64
}
65

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Given an n x m grid with walls '#', empty '.', and hazard cells 'H',
5
// compute the minimal time (steps) for hazard to reach each cell moving in 4 directions.
6
// All hazard cells start simultaneously at time 0.
7
// Input:
8
// n m
9
// n lines of grid
10
// Output: the distance grid with -1 for unreachable cells (e.g., blocked components).
11
12
int main() {
13
    ios::sync_with_stdio(false);
14
    cin.tie(nullptr);
15
16
    int n, m; 
17
    if (!(cin >> n >> m)) return 0;
18
    vector<string> g(n);
19
    for (int i = 0; i < n; ++i) cin >> g[i];
20
21
    const int INF = 1e9;
22
    vector<vector<int>> dist(n, vector<int>(m, INF));
23
    queue<pair<int,int>> q;
24
25
    // Initialize sources: all 'H' cells
26
    for (int i = 0; i < n; ++i) {
27
        for (int j = 0; j < m; ++j) {
28
            if (g[i][j] == 'H') {
29
                dist[i][j] = 0;
30
                q.push({i, j});
31
            }
32
        }
33
    }
34
35
    auto inside = [&](int x, int y){ return 0 <= x && x < n && 0 <= y && y < m; };
36
    int dx[4] = {-1, 1, 0, 0};
37
    int dy[4] = {0, 0, -1, 1};
38
39
    while (!q.empty()) {
40
        auto [x, y] = q.front(); q.pop();
41
        for (int dir = 0; dir < 4; ++dir) {
42
            int nx = x + dx[dir];
43
            int ny = y + dy[dir];
44
            if (!inside(nx, ny)) continue;
45
            if (g[nx][ny] == '#') continue; // walls block movement
46
            if (dist[nx][ny] != INF) continue; // already visited
47
            dist[nx][ny] = dist[x][y] + 1;
48
            q.push({nx, ny});
49
        }
50
    }
51
52
    for (int i = 0; i < n; ++i) {
53
        for (int j = 0; j < m; ++j) {
54
            int ans = (dist[i][j] == INF ? -1 : dist[i][j]);
55
            cout << ans << (j + 1 == m ? '\n' : ' ');
56
        }
57
    }
58
}
59

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Multi-source BFS that also records which source reached each node first
5
// and allows reconstructing a shortest path from a query node to its nearest source.
6
// Input:
7
// n m
8
// m lines: u v (1-based, undirected)
9
// k
10
// k lines: s_i (1-based sources)
11
// q (number of queries), followed by q nodes t_j to reconstruct paths for.
12
// Output: for each query, either the path length and path, or -1 if unreachable.
13
14
int main() {
15
    ios::sync_with_stdio(false);
16
    cin.tie(nullptr);
17
18
    int n, m; if (!(cin >> n >> m)) return 0;
19
    vector<vector<int>> adj(n);
20
    for (int i = 0; i < m; ++i) {
21
        int u, v; cin >> u >> v; --u; --v;
22
        adj[u].push_back(v);
23
        adj[v].push_back(u);
24
    }
25
    int k; cin >> k;
26
    vector<int> sources(k);
27
    for (int i = 0; i < k; ++i) { cin >> sources[i]; --sources[i]; }
28
29
    const int INF = 1e9;
30
    vector<int> dist(n, INF), parent(n, -1), src_id(n, -1);
31
    queue<int> q;
32
33
    // Initialize all sources: tie-break by smaller source index
34
    // If duplicates exist, they are ignored by dist check.
35
    for (int i = 0; i < k; ++i) {
36
        int s = sources[i];
37
        if (dist[s] == 0) continue;
38
        dist[s] = 0;
39
        parent[s] = -1; // root of its tree
40
        src_id[s] = i;  // remember which source index
41
        q.push(s);
42
    }
43
44
    while (!q.empty()) {
45
        int u = q.front(); q.pop();
46
        for (int v : adj[u]) {
47
            if (dist[v] == INF) {
48
                dist[v] = dist[u] + 1;
49
                parent[v] = u;
50
                src_id[v] = src_id[u];
51
                q.push(v);
52
            }
53
        }
54
    }
55
56
    int qn; cin >> qn;
57
    while (qn--) {
58
        int t; cin >> t; --t;
59
        if (dist[t] == INF) {
60
            cout << -1 << '\n';
61
            continue;
62
        }
63
        // Reconstruct path from t back to its nearest source using parent[]
64
        vector<int> path;
65
        int cur = t;
66
        while (cur != -1) {
67
            path.push_back(cur);
68
            cur = parent[cur];
69
        }
70
        reverse(path.begin(), path.end());
71
        cout << "length=" << (int)path.size() - 1
72
             << " source_index=" << src_id[t] << " path:";
73
        for (int v : path) cout << ' ' << (v + 1);
74
        cout << '\n';
75
    }
76
}
77