0-1 BFS

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Solves single-source shortest paths on a graph with edge weights 0 or 1
5
// Input format example:
6
// n m s
7
// u v w (m lines, 0-indexed vertices, weight w in {0,1})
8
// Prints distances from s to every vertex (INF if unreachable)
9
10
int main() {
11
    ios::sync_with_stdio(false);
12
    cin.tie(nullptr);
13
14
    int n, m, s;
15
    if (!(cin >> n >> m >> s)) return 0;
16
    vector<vector<pair<int,int>>> g(n);
17
    for (int i = 0; i < m; ++i) {
18
        int u, v, w; cin >> u >> v >> w;
19
        // Directed edge u -> v with weight w in {0,1}
20
        g[u].push_back({v, w});
21
        // If the graph is undirected, also add g[v].push_back({u, w});
22
    }
23
24
    const int INF = 1e9;
25
    vector<int> dist(n, INF);
26
    deque<int> dq;
27
28
    dist[s] = 0;
29
    dq.push_front(s);
30
31
    while (!dq.empty()) {
32
        int u = dq.front(); dq.pop_front();
33
        for (auto [v, w] : g[u]) {
34
            // Relaxation: try to improve dist[v]
35
            if (dist[v] > dist[u] + w) {
36
                dist[v] = dist[u] + w;
37
                if (w == 0) dq.push_front(v); else dq.push_back(v);
38
            }
39
        }
40
    }
41
42
    for (int i = 0; i < n; ++i) {
43
        if (dist[i] == INF) cout << "INF\n"; else cout << dist[i] << "\n";
44
    }
45
    return 0;
46
}
47

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Given an n x m grid of characters:
5
// '.' means free cell (entering costs 0)
6
// '#' means wall (entering costs 1)
7
// Move in 4 directions. Start at (0,0), target at (n-1,m-1).
8
// Find the minimum number of walls to break to reach the target.
9
10
int main() {
11
    ios::sync_with_stdio(false);
12
    cin.tie(nullptr);
13
14
    int n, m; 
15
    if (!(cin >> n >> m)) return 0;
16
    vector<string> grid(n);
17
    for (int i = 0; i < n; ++i) cin >> grid[i];
18
19
    const int INF = 1e9;
20
    vector<vector<int>> dist(n, vector<int>(m, INF));
21
22
    auto inside = [&](int r, int c){ return r >= 0 && r < n && c >= 0 && c < m; };
23
24
    deque<pair<int,int>> dq;
25
    dist[0][0] = (grid[0][0] == '#'); // cost to enter start cell (often 0 if ensured '.')
26
    dq.push_front({0,0});
27
28
    int dr[4] = {-1, 1, 0, 0};
29
    int dc[4] = {0, 0, -1, 1};
30
31
    while (!dq.empty()) {
32
        auto [r, c] = dq.front(); dq.pop_front();
33
        for (int k = 0; k < 4; ++k) {
34
            int nr = r + dr[k], nc = c + dc[k];
35
            if (!inside(nr, nc)) continue;
36
            int w = (grid[nr][nc] == '#') ? 1 : 0; // cost to enter next cell
37
            if (dist[nr][nc] > dist[r][c] + w) {
38
                dist[nr][nc] = dist[r][c] + w;
39
                if (w == 0) dq.push_front({nr, nc}); else dq.push_back({nr, nc});
40
            }
41
        }
42
    }
43
44
    int ans = dist[n-1][m-1];
45
    if (ans >= INF) cout << -1 << "\n"; else cout << ans << "\n";
46
    return 0;
47
}
48

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Multi-source 0-1 BFS: distances from any source in S to all nodes, with path reconstruction to target t.
5
// Input example:
6
// n m k
7
// s1 s2 ... sk (k sources)
8
// u v w (m lines, directed, w in {0,1})
9
// t (target)
10
11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
15
    int n, m, k; 
16
    if (!(cin >> n >> m >> k)) return 0;
17
    vector<int> sources(k);
18
    for (int i = 0; i < k; ++i) cin >> sources[i];
19
    vector<vector<pair<int,int>>> g(n);
20
    for (int i = 0; i < m; ++i) {
21
        int u, v, w; cin >> u >> v >> w; 
22
        g[u].push_back({v, w});
23
    }
24
    int t; cin >> t;
25
26
    const int INF = 1e9;
27
    vector<int> dist(n, INF), par(n, -1), parW(n, -1);
28
    deque<int> dq;
29
30
    // Initialize all sources with distance 0
31
    for (int s : sources) {
32
        if (dist[s] > 0) {
33
            dist[s] = 0;
34
            dq.push_front(s);
35
        }
36
    }
37
38
    while (!dq.empty()) {
39
        int u = dq.front(); dq.pop_front();
40
        for (auto [v, w] : g[u]) {
41
            if (dist[v] > dist[u] + w) {
42
                dist[v] = dist[u] + w;
43
                par[v] = u;         // store predecessor for path reconstruction
44
                parW[v] = w;        // store edge weight used
45
                if (w == 0) dq.push_front(v); else dq.push_back(v);
46
            }
47
        }
48
    }
49
50
    if (dist[t] >= INF) {
51
        cout << "No path\n";
52
        return 0;
53
    }
54
55
    // Reconstruct one shortest path to t
56
    vector<int> path;
57
    for (int v = t; v != -1; v = par[v]) path.push_back(v);
58
    reverse(path.begin(), path.end());
59
60
    cout << "Distance: " << dist[t] << "\n";
61
    cout << "Path (" << path.size() << " nodes): ";
62
    for (int i = 0; i < (int)path.size(); ++i) cout << path[i] << (i+1==(int)path.size()? '\n' : ' ');
63
64
    // Optional: print edge weights along the path
65
    cout << "Edge weights along path: ";
66
    for (int i = 1; i < (int)path.size(); ++i) cout << parW[path[i]] << (i+1==(int)path.size()? '\n' : ' ');
67
68
    return 0;
69
}
70