アルゴリズム基礎テンプレート

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

bool check(int x) {/* ... */} // xがある性質を満たすかどうかをチェック

// 区間[l, r]が[l, mid]と[mid + 1, r]に分割される場合：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()はmidが性質を満たすかどうかを判断
        else l = mid + 1;
    }
    return l;
}
// 区間[l, r]が[l, mid - 1]と[mid, r]に分割される場合：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

bool check(double x) {/* ... */} // xがある性質を満たすかどうかをチェック

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // epsは精度を示し、問題の精度要求に依存
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// C = A - B, 満たすA >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

1
2

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

1
2
3

S[i, j] = 第i行j列の左上部分の全ての要素の和
(x1, y1)を左上角、(x2, y2)を右下角とする子行列の和は：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

1
2

(x1, y1)を左上角、(x2, y2)を右下角とする子行列の全ての要素にcを加える：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

1
2

nの第k位の数字を求める: n >> k & 1
nの最後の1を返す：lowbit(n) = n & -n

1
2
3
4
5
6
7
8
9

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体的な問題のロジック
}
一般的な問題の分類：
    (1) あるシーケンスに対して、2つのポインタで区間を維持
    (2) 2つのシーケンスに対して、ある種の順序を維持、例えばマージソートで2つのソート済みシーケンスをマージする操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

vector<int> alls; // 全ての離散化する値を格納
sort(alls.begin(), alls.end()); // 全ての値をソート
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 重複要素を削除

// 二分探索でxに対応する離散化された値を求める
int find(int x) // x以上の最小の位置を見つける
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 1, 2, ...nにマッピング
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// 全ての交差する区間をマージ
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// headはリンクリストの頭を保存し、e[]はノードの値を保存し、ne[]はノードのnextポインタを保存し、idxは現在どのノードを使用しているかを示す
int head, e[N], ne[N], idx;

// 初期化
void init()
{
    head = -1;
    idx = 0;
}

// リンクリストの頭に数aを挿入
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 頭ノードを削除、頭ノードが存在することを保証する必要がある
void remove()
{
    head = ne[head];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// e[]はノードの値を示し、l[]はノードの左ポインタを示し、r[]はノードの右ポインタを示し、idxは現在どのノードを使用しているかを示す
int e[N], l[N], r[N], idx;

// 初期化
void init()
{
    //0は左端点、1は右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// ノードaの右側に数xを挿入
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// ノードaを削除
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// ttはスタックトップを示す
int stk[N], tt = 0;

// スタックトップに数を挿入
stk[ ++ tt] = x;

// スタックトップから数をポップ
tt -- ;

// スタックトップの値
stk[tt];

// スタックが空かどうかを判断、tt > 0の場合、空でないことを示す
if (tt > 0)
{

}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// hhはキューヘッドを示し、ttはキューの末尾を示す
int q[N], hh = 0, tt = -1;

// キューの末尾に数を挿入
q[ ++ tt] = x;

// キューヘッドから数をポップ
hh ++ ;

// キューヘッドの値
q[hh];

// キューが空かどうかを判断、hh <= ttの場合、空でないことを示す
if (hh <= tt)
{
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// hhはキューヘッドを示し、ttはキューの末尾の次の位置を示す
int q[N], hh = 0, tt = 0;

// キューの末尾に数を挿入
q[tt ++ ] = x;
if (tt == N) tt = 0;

// キューヘッドから数をポップ
hh ++ ;
if (hh == N) hh = 0;

// キューヘッドの値
q[hh];

// キューが空かどうかを判断、hh != ttの場合、空でないことを示す
if (hh != tt)
{
}

1
2
3
4
5
6

int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

1
2
3
4
5
6
7

int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // キューヘッドがウィンドウから滑り出たかどうかを判断
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// s[]は長いテキスト、p[]はパターン文字列、nはsの長さ、mはpの長さ
パターン文字列のNext配列を求める：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// マッチング
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // マッチング成功後のロジック
    }
}//Cのライブラリ関数 strstr()も同様

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

int son[N][26], cnt[N], idx;
// 0番目の点は根ノードであり、空ノードでもある
// son[][]は木の各ノードの子ノードを保存
// cnt[]は各ノードで終わる単語の数を保存

// 文字列を挿入
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 文字列の出現回数を検索
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}//map<string,int>を使うこともできるが、時間は2倍以上かかる

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

    int p[N]; //各点の祖先ノードを保存

    // xの祖先ノードを返す
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初期化、ノード番号は1~nと仮定
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // aとbが属する2つの集合を併合：
    p[find(a)] = find(b);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

    int p[N], size[N];
    //p[]は各点の祖先ノードを保存し、size[]は祖先ノードのみに意味があり、祖先ノードが属する集合中の点の数を示す

    // xの祖先ノードを返す
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初期化、ノード番号は1~nと仮定
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // aとbが属する2つの集合を併合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

    int p[N], d[N];
    //p[]は各点の祖先ノードを保存し、d[x]はxからp[x]への距離を保存

    // xの祖先ノードを返す
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初期化、ノード番号は1~nと仮定
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // aとbが属する2つの集合を併合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 具体的な問題に基づいて、find(a)のオフセットを初期化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// h[N]はヒープ中の値を保存し、h[1]はヒープトップであり、xの左子は2x、右子は2x + 1
// ph[k]はk番目に挿入された点がヒープ中のどの位置にあるかを保存
// hp[k]はヒープ中のインデックスがkの点が何番目に挿入されたかを保存
int h[N], ph[N], hp[N], size;

// 2つの点とそのマッピング関係を交換
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)でヒープを構築
for (int i = n / 2; i; i -- ) down(i);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

(1) チェイン法
    int h[N], e[N], ne[N], idx;

    // ハッシュテーブルに数を挿入
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // ハッシュテーブルに特定の数が存在するかどうかを検索
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;

        return false;
    }

(2) オープンアドレス法
    int h[N];

    // xがハッシュテーブルに存在する場合、xのインデックスを返す。xがハッシュテーブルに存在しない場合、xを挿入すべき位置を返す
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]は文字列の最初のk文字のハッシュ値を保存し、p[k]は P^k mod 2^64を保存

// 初期化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 部分文字列 str[l ~ r] のハッシュ値を計算
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

vector, 可変長配列、倍増の考え方
    size()  要素数を返す
    empty()  空かどうかを返す
    clear()  クリア
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    辞書順で比較演算をサポート

pair<int, int>
    first, 最初の要素
    second, 2番目の要素
    比較演算をサポートし、firstを第1キー、secondを第2キー（辞書順）として使用

string, 文字列
    size()/length()  文字列の長さを返す
    empty()
    clear()
    substr(開始インデックス、(部分文字列の長さ))  部分文字列を返す
    c_str()  文字列が格納されている文字配列の開始アドレスを返す

queue, キュー
    size()
    empty()
    push()  キューの末尾に要素を挿入
    front()  キューヘッドの要素を返す
    back()  キューの末尾の要素を返す
    pop()  キューヘッドの要素をポップ

priority_queue, 優先度キュー、デフォルトは大根ヒープ
    size()
    empty()
    push()  要素を挿入
    top()  ヒープトップの要素を返す
    pop()  ヒープトップの要素をポップ
    小根ヒープとして定義する方法：priority_queue<int, vector<int>, greater<int>> q;

stack, スタック
    size()
    empty()
    push()  スタックトップに要素を挿入
    top()  スタックトップの要素を返す
    pop()  スタックトップの要素をポップ

deque, 両端キュー
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 平衡二分木（赤黒木）に基づき、有序列を動的に維持
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 前駆と後継を返し、時間複雑度は O(logn)

    set/multiset
        insert()  数を挿入
        find()  数を検索
        count()  特定の数の個数を返す
        erase()
            (1) 入力が数xの場合、全てのxを削除   O(k + logn)
            (2) 入力がイテレータの場合、そのイテレータを削除
        lower_bound()/upper_bound()
            lower_bound(x)  x以上の最小の数のイテレータを返す
            upper_bound(x)  xより大きい最小の数のイテレータを返す
    map/multimap
        insert()  挿入する数はpair
        erase()  入力はpairまたはイテレータ
        find()
        []  注意：multimapはこの操作をサポートしない。 時間複雑度は O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, ハッシュテーブル
    上記と類似し、増減改削の時間複雑度は O(1)
    lower_bound()/upper_bound()、イテレータの++、--をサポートしない

bitset, 圧縮
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  1の数を返す

    any()  少なくとも1つの1があるかどうかを判断
    none()  全て0かどうかを判断

    set()  全ての位置を1にする
    set(k, v)  第k位をvにする
    reset()  全ての位置を0にする
    flip()  ~と等価
    flip(k) 第k位を反転

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// 各点kに対して、単一リンクリストを開き、kから到達可能な全ての点を保存します。h[k]はこの単一リンクリストの頭ノードを保存します
int h[N], e[N], ne[N], idx;

// 辺a->bを追加
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初期化
idx = 0;
memset(h, -1, sizeof h);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int dfs(int u)
{
    st[u] = true; // st[u] は点uが既に遍歴されたかどうかを示します

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

queue<int> q;
st[1] = true; // 1番目の点が既に遍歴されたことを示します
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 点jが既に遍歴されたことを示します
            q.push(j);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] は点iの入次数を保存します
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    // 全ての点がキューに入った場合、トポロジカルシーケンスが存在することを示します。そうでない場合、トポロジカルシーケンスは存在しません。
    return tt == n - 1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

int g[N][N];  // 全ての辺を保存
int dist[N];  // 1番目の点から各点への最短距離を保存
bool st[N];   // 各点の最短経路が既に確定したかどうかを保存

// 1番目の点からn番目の点への最短経路を求めます。存在しない場合は-1を返します
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // まだ最短経路が確定していない点の中で、距離が最小の点を探します
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // tを用いて他の点の距離を更新します
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

typedef pair<int, int> PII;

int n;      // 点の数
int h[N], w[N], e[N], ne[N], idx;       // 隣接リストで全ての辺を保存
int dist[N];        // 各点から1番目の点への距離を保存
bool st[N];     // 各点の最短距離が既に確定したかどうかを保存

// 1番目の点からn番目の点への最短距離を求めます。1番目の点からn番目の点に到達できない場合は-1を返します
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // firstは距離を保存し、secondはノード番号を保存します

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int n, m;       // nは点数を示し、mは辺数を示します
int dist[N];        // dist[x]は1からxへの最短経路距離を保存

struct Edge     // 辺、aは出発点、bは到達点、wは辺の重みを示します
{
    int a, b, w;
}edges[M];

// 1からnへの最短経路距離を求めます。1からnに到達できない場合は-1を返します。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // n回目の反復でも三角不等式が緩和される場合、長さがn+1の最短経路が存在することを示し、抽斗原理により、経路中に少なくとも2つの同じ点が存在するため、負の重みのサイクルが存在することを示します。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

int n;      // 総点数
int h[N], w[N], e[N], ne[N], idx;       // 隣接リストで全ての辺を保存
int dist[N];        // 各点から1番目の点への最短距離を保存
bool st[N];     // 各点がキューに入っているかどうかを保存

// 1番目の点からn番目の点への最短経路距離を求めます。1番目の点からn番目の点に到達できない場合は-1を返します
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // jが既にキューに存在する場合、jを重複して挿入する必要はありません
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

int n;      // 総点数
int h[N], w[N], e[N], ne[N], idx;       // 隣接リストで全ての辺を保存
int dist[N], cnt[N];        // dist[x]は1番目の点からxへの最短距離を保存し、cnt[x]は1からxへの最短経路に含まれる点数を保存
bool st[N];     // 各点がキューに入っているかどうかを保存

// 負のサイクルが存在する場合はtrueを返し、そうでない場合はfalseを返します。
bool spfa()
{
    // dist配列を初期化する必要はありません
    // 原理：ある最短経路にn個の点がある場合（自分を除く）、自分を加えるとn+1個の点があり、抽斗原理により、少なくとも2つの点が同じであるため、サイクルが存在することを示します。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 1番目の点からxへの最短経路に少なくともn個の点が含まれる場合（自分を除く）、サイクルが存在することを示します
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}