Basic Algorithm Templates

 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) {/* ... */} // Check if x satisfies a certain property

// When the interval [l, r] is divided into [l, mid] and [mid + 1, r]:
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check() determines if mid satisfies the property
        else l = mid + 1;
    }
    return l;
}
// When the interval [l, r] is divided into [l, mid - 1] and [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) {/* ... */} // Check if x satisfies a certain property

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps represents the precision, depending on the precision requirement of the problem
    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, satisfying 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] = Sum of all elements in the upper left part of the grid at row i and column j
The sum of the submatrix with (x1, y1) as the upper left corner and (x2, y2) as the lower right corner is:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

1
2

Add c to all elements in the submatrix with (x1, y1) as the upper left corner and (x2, y2) as the lower right corner:
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

1
2

Find the k-th digit of n: n >> k & 1
Return the last 1 of n: 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 ++ ;

    // Logic for specific problem
}
Common problem categories:
    (1) For a sequence, maintain an interval with two pointers
    (2) For two sequences, maintain a certain order, such as merging two ordered sequences in merge sort

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

vector<int> alls; // Store all values to be discretized
sort(alls.begin(), alls.end()); // Sort all values
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // Remove duplicate elements

// Binary search to find the discretized value corresponding to x
int find(int x) // Find the first position greater than or equal to 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; // Map to 1, 2, ...n
}

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

// Merge all intervals that have intersections
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 stores the head of the linked list, e[] stores the value of the node, ne[] stores the next pointer of the node, idx indicates which node is currently used
int head, e[N], ne[N], idx;

// Initialization
void init()
{
    head = -1;
    idx = 0;
}

// Insert a number a at the head of the linked list
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// Delete the head node, need to ensure the head node exists
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[] represents the value of the node, l[] represents the left pointer of the node, r[] represents the right pointer of the node, idx indicates which node is currently used
int e[N], l[N], r[N], idx;

// Initialization
void init()
{
    //0 is the left endpoint, 1 is the right endpoint
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// Insert a number x to the right of node a
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// Delete node 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 indicates the top of the stack
int stk[N], tt = 0;

// Insert a number to the top of the stack
stk[ ++ tt] = x;

// Pop a number from the top of the stack
tt -- ;

// Value at the top of the stack
stk[tt];

// Check if the stack is empty, if tt > 0, it means not empty
if (tt > 0)
{

}

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

// hh indicates the head of the queue, tt indicates the tail of the queue
int q[N], hh = 0, tt = -1;

// Insert a number to the tail of the queue
q[ ++ tt] = x;

// Pop a number from the head of the queue
hh ++ ;

// Value at the head of the queue
q[hh];

// Check if the queue is empty, if hh <= tt, it means not empty
if (hh <= tt)
{
}

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

// hh indicates the head of the queue, tt indicates the position after the tail of the queue
int q[N], hh = 0, tt = 0;

// Insert a number to the tail of the queue
q[tt ++ ] = x;
if (tt == N) tt = 0;

// Pop a number from the head of the queue
hh ++ ;
if (hh == N) hh = 0;

// Value at the head of the queue
q[hh];

// Check if the queue is empty, if hh != tt, it means not empty
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 ++ ;  // Check if the head of the queue slides out of the window
    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[] is the long text, p[] is the pattern string, n is the length of s, m is the length of p
Compute the Next array of the pattern string:
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;
}

// Matching
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];
        // Logic after successful match
    }
}//C's library function strstr() is like this

 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;
// Node 0 is both the root node and the empty node
// son[][] stores the child nodes of each node in the tree
// cnt[] stores the number of words ending at each node

// Insert a string
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] ++ ;
}

// Query the number of occurrences of a string
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];
}//You can use map<string,int>, but the time is more than twice

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

    int p[N]; // Store the ancestor node of each point

    // Return the ancestor node of x
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // Initialization, assuming node numbers are 1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // Merge the two sets where a and b are located:
    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[] stores the ancestor node of each point, size[] is only meaningful for ancestor nodes, indicating the number of points in the set where the ancestor node is located

    // Return the ancestor node of x
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // Initialization, assuming node numbers are 1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // Merge the two sets where a and b are located:
    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[] stores the ancestor node of each point, d[x] stores the distance from x to p[x]

    // Return the ancestor node of 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];
    }

    // Initialization, assuming node numbers are 1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // Merge the two sets where a and b are located:
    p[find(a)] = find(b);
    d[find(a)] = distance; // Initialize the offset of find(a) according to the specific problem

 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] stores the values in the heap, h[1] is the top of the heap, the left child of x is 2x, the right child is 2x + 1
// ph[k] stores the position of the k-th inserted point in the heap
// hp[k] stores the k-th point in the heap is the k-th inserted
int h[N], ph[N], hp[N], size;

// Swap two points and their mapping relationships
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) build heap
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) Chaining Method
    int h[N], e[N], ne[N], idx;

    // Insert a number into the hash table
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // Query whether a number exists in the hash table
    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) Open Addressing Method
    int h[N];

    // If x is in the hash table, return the index of x; if x is not in the hash table, return the position where x should be inserted
    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] stores the hash value of the first k letters of the string, p[k] stores P^k mod 2^64

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

// Calculate the hash value of the substring 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, Dynamic array, doubling idea
    size()  Return the number of elements
    empty()  Return whether it is empty
    clear()  Clear
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    Support comparison operations, in lexicographical order

pair<int, int>
    first, First element
    second, Second element
    Support comparison operations, with first as the first key, second as the second key (lexicographical order)

string, String
    size()/length()  Return the length of the string
    empty()
    clear()
    substr(start index, (substring length))  Return substring
    c_str()  Return the starting address of the character array where the string is located

queue, Queue
    size()
    empty()
    push()  Insert an element to the tail
    front()  Return the head element
    back()  Return the tail element
    pop()  Pop the head element

priority_queue, Priority queue, default is max heap
    size()
    empty()
    push()  Insert an element
    top()  Return the top element
    pop()  Pop the top element
    Define as min heap: priority_queue<int, vector<int>, greater<int>> q;

stack, Stack
    size()
    empty()
    push()  Insert an element to the top
    top()  Return the top element
    pop()  Pop the top element

deque, Double-ended queue
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, Based on balanced binary tree (red-black tree), dynamically maintain ordered sequence
    size()
    empty()
    clear()
    begin()/end()
    ++, -- Return predecessor and successor, time complexity O(logn)

    set/multiset
        insert()  Insert a number
        find()  Find a number
        count()  Return the number of a certain number
        erase()
            (1) Input is a number x, delete all x   O(k + logn)
            (2) Input an iterator, delete this iterator
        lower_bound()/upper_bound()
            lower_bound(x)  Return the iterator of the smallest number greater than or equal to x
            upper_bound(x)  Return the iterator of the smallest number greater than x
    map/multimap
        insert()  Inserted number is a pair
        erase()  Input parameter is pair or iterator
        find()
        []  Note that multimap does not support this operation. Time complexity is O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, Hash table
    Similar to the above, the time complexity of addition, deletion, modification, and query is O(1)
    Does not support lower_bound()/upper_bound(), iterator's ++, --

bitset, Bit compression
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  Return how many 1s

    any()  Check if there is at least one 1
    none()  Check if all are 0

    set()  Set all positions to 1
    set(k, v)  Set the k-th bit to v
    reset()  Set all bits to 0
    flip()  Equivalent to ~
    flip(k) Invert the k-th bit

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

// For each point k, open a singly linked list to store all points that k can reach. h[k] stores the head node of this singly linked list
int h[N], e[N], ne[N], idx;

// Add an edge a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// Initialization
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] indicates that point u has been traversed

    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; // Indicates that point 1 has been traversed
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; // Indicates that point j has been traversed
            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] stores the in-degree of point 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;
        }
    }

    // If all points are enqueued, it means there is a topological sequence; otherwise, there is no topological sequence.
    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];  // Store each edge
int dist[N];  // Store the shortest distance from point 1 to each point
bool st[N];   // Store whether the shortest path of each point has been determined

// Find the shortest path from point 1 to point n, if it does not exist, return -1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // Find the point with the smallest distance among the points whose shortest path has not been determined
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // Use t to update the distance of other points
        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;      // Number of points
int h[N], w[N], e[N], ne[N], idx;       // Adjacency list stores all edges
int dist[N];        // Store the distance from each point to point 1
bool st[N];     // Store whether the shortest distance of each point has been determined

// Find the shortest path from point 1 to point n, if it does not exist, return -1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first stores the distance, second stores the node number

    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 represents the number of points, m represents the number of edges
int dist[N];        // dist[x] stores the shortest path distance from 1 to x

struct Edge     // Edge, a represents the starting point, b represents the ending point, w represents the weight of the edge
{
    int a, b, w;
}edges[M];

// Find the shortest path distance from 1 to n, if it is impossible to go from 1 to n, return -1.
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // If the n-th iteration still relaxes the triangle inequality, it means that there is a shortest path of length n+1, and by the pigeonhole principle, there are at least two identical points in the path, indicating that there is a negative weight cycle in the graph.
    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;      // Total number of points
int h[N], w[N], e[N], ne[N], idx;       // Adjacency list stores all edges
int dist[N];        // Store the shortest distance from each point to point 1
bool st[N];     // Store whether each point is in the queue

// Find the shortest path distance from point 1 to point n, if it is impossible to go from point 1 to point n, return -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])     // If j already exists in the queue, do not insert j repeatedly
                {
                    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