graph/bfs01.cpp

• View this file on GitHub
• Last update: 2022-08-28 17:14:39+09:00
• Link: https://atcoder.jp/contests/arc005/submissions/34363432

Code

#pragma once
#include <bits/stdc++.h>
using namespace std;

// https://atcoder.jp/contests/arc005/submissions/34363432

// Bfs01
// nは頂点数, Gは隣接リストで隣接頂点とその頂点との距離(0 or 1)をもつ
struct Bfs01 {
    int n;
    vector<vector<pair<int, int>>> G;
    vector<int> dist;

    Bfs01(int n, vector<vector<pair<int, int>>> &G) : n(n), G(G) {
        dist.assign(n, -1);
    }

    // shortest_path
    // 頂点sからの最短経路を求める.
    // 制約: 0 <= s < n
    void shortest_path(int s) {
        fill(dist.begin(), dist.end(), -1);
        dist[s] = 0;

        deque<int> q;
        q.push_back(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop_front();
            for (auto &p : G[v]) {
                auto [u, c] = p;
                if (dist[u] >= 0) continue;
                dist[u] = dist[v] + c;
                if (c == 0)
                    q.push_front(u);
                else
                    q.push_back(u);
            }
        }
    }
};

#line 2 "graph/bfs01.cpp"
#include <bits/stdc++.h>
using namespace std;

// https://atcoder.jp/contests/arc005/submissions/34363432

// Bfs01
// nは頂点数, Gは隣接リストで隣接頂点とその頂点との距離(0 or 1)をもつ
struct Bfs01 {
    int n;
    vector<vector<pair<int, int>>> G;
    vector<int> dist;

    Bfs01(int n, vector<vector<pair<int, int>>> &G) : n(n), G(G) {
        dist.assign(n, -1);
    }

    // shortest_path
    // 頂点sからの最短経路を求める.
    // 制約: 0 <= s < n
    void shortest_path(int s) {
        fill(dist.begin(), dist.end(), -1);
        dist[s] = 0;

        deque<int> q;
        q.push_back(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop_front();
            for (auto &p : G[v]) {
                auto [u, c] = p;
                if (dist[u] >= 0) continue;
                dist[u] = dist[v] + c;
                if (c == 0)
                    q.push_front(u);
                else
                    q.push_back(u);
            }
        }
    }
};

Back to top page