Algorithm Basics Template

 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) {/* ... */} // Checks whether x satisfies some 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 meets the criteria
        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) {/* ... */} // Checks whether x satisfies some property

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps represents precision, depending on the problem's requirements
    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

// 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;
    }

1
2
3

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, provided 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 cell at row i and column j
The sum of a 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

To add c to every element in the submatrix whose upper left corner is (x1, y1) and lower right corner is (x2, y2):
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

1
2

To get the k-th digit of n: n >> k & 1
Return the last bit 1 of n: lowbit(n) = n & -n

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

    // logic specific to the problem
}
Common problem categories:

1. For a sequence, use two pointers to maintain a range
2. For two sequences, maintain some kind of order, like merging two ordered sequences in merge sort

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

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


```cpp
// Use binary search to find the discretized value corresponding to x
int find(int x) // Find the first position that is 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 with 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 list, e[] stores the value of the node, ne[] stores the next pointer of the node, idx indicates the current node in use
int head, e[N], ne[N], idx;

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

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

// Remove the head node, ensuring 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 the current node in use
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 represents the top of the stack
int stk[N], tt = 0;

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

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

// The value at the top of the stack
stk[tt];

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

}

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

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

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

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

// The value at the head of the queue
q[hh];

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

1
2

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

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

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

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

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

// Check if the queue is empty, if hh != tt, then it is 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
Calculate 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 a successful match
    }
}//The C library function strstr() works in the same way

 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 null node
// son[][] stores the children of each node in the tree
// cnt[] stores the number of words ending in 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];
}//It's possible to use map<string,int>, but the timing would be more than twice as slow

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

    int p[N]; //Stores 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 a and b belong to:
    p[find(a)] = find(b);

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

    int p[N], size[N];
    //p[] stores the ancestor node of each point, size[] only has meaning for ancestor nodes, indicating the number of points in the set the ancestor node belongs to

    // 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;
    }

1
2
3

// Merge the two sets to which a and b belong:
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
26
27

(3) Union-find set maintaining the distance to the ancestor node:
```cpp
    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 the node numbers are 1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // Merge the two sets that a and b belong to:
    p[find(a)] = find(b);
    d[find(a)] = distance; // Initialize the offset of find(a) based on 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 heap top, the left child of x is 2x, the right child is 2x + 1
// ph[k] stores the position in the heap of the kth inserted point
// hp[k] stores which insert order the point at index k in the heap was
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
    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 ++ ;
    }

    // Check if 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
    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 insertion position for 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

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;
}

1
2
3
4
5

// 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, idea of doubling
    size()  Returns the number of elements
    empty()  Returns whether it is empty
    clear()  Clears
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    Supports comparison operations, ordered by lexicographical order

pair<int, int>
    first, the first element
    second, the second element
    Supports comparison operations, with first as the primary key and second as the secondary key (lexicographical order)

string, string
    size()/length()  Returns the length of the string
    empty()
    clear()
    substr(start index, (substring length))  Returns substring
    c_str()  Returns the address of the start of the character array containing the string

queue, queue
    size()
    empty()
    push()  Inserts an element at the end of the queue
    front()  Returns the front element
    back()  Returns the back element
    pop()  Pops the front element

priority_queue, priority queue, default is a max heap
    size()
    empty()
    push()  Inserts an element
    top()  Returns the top element
    pop()  Pops the top element
    To define as a min heap: priority_queue<int, vector<int>, greater<int>> q;

stack, stack
    size()
    empty()
    push()  Inserts an element at the top of the stack
    top()  Returns the top element
    pop()  Pops 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 maintaining ordered sequence
    size()
    empty()
    clear()
    begin()/end()
    ++, -- Returns the predecessor and successor, time complexity O(logn)

    set/multiset
        insert()  Inserts a number
        find()  Searches for a number
        count()  Returns the count of a specific number
        erase()
            (1) Input is a number x, deletes all x   O(k + logn)
            (2) Input is an iterator, deletes the iterator
        lower_bound()/upper_bound()
            lower_bound(x)  Returns an iterator to the smallest number that is greater than or equal to x
            upper_bound(x)  Returns an iterator to the smallest number that is greater than x
    map/multimap
        insert()  Insertion is a pair
        erase()  Input parameter is a pair or an 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 above, time complexity of CRUD operations is O(1)
    Does not support lower_bound()/upper_bound(), iterator's ++, --

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

    count()  Returns the number of ones

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

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

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

// For each point k, open a linked list, storing all points that k can reach. h[k] stores the head of this 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 vertex 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 vertex 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 vertex 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 vertex 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 vertices have been enqueued, a topological order exists; otherwise, it does not exist.
    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];  // Stores each edge
int dist[N];  // Stores the shortest distance from vertex 1 to every other vertex
bool st[N];   // Stores whether the shortest path for each vertex has been determined

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

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // Among the vertices whose shortest path has not been determined, find the one with the minimum distance
        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 vertices
        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
40
41

typedef pair<int, int> PII;

int n;      // Number of vertices
int h[N], w[N], e[N], ne[N], idx;       // Adjacency list to store all edges
int dist[N];        // Stores the distance of all vertices from vertex 1
bool st[N];     // Stores whether the shortest distance for each vertex has been determined

// Seeks the shortest distance from vertex 1 to vertex n, returns -1 if it does not exist
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 vertex number

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

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


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

struct Edge     // Edge, a is the start vertex, b is the end vertex, w is the weight of the edge
{
    int a, b, w;
}edges[M];

// Finds the shortest path distance from 1 to n; returns -1 if it's not possible to travel from 1 to n.
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // If the triangle inequality is still relaxed in the nth iteration, it means there exists a shortest path with length n+1. According to the pigeonhole principle, there must be at least two identical points on the path, indicating that the graph contains a negative weight cycle.
    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 vertices
int h[N], w[N], e[N], ne[N], idx;       // Adjacency list to store all edges
int dist[N];        // Stores the shortest distance from vertex 1 to each vertex
bool st[N];     // Stores whether each vertex is in the queue

// Finds the shortest path distance from vertex 1 to n; returns -1 if it's not possible to walk from 1 to n.
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 is already in the queue, there's no need to insert j again
                {
                    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

int n;      // Total number of vertices
int h[N], w[N], e[N], ne[N], idx;       // Adjacency list to store all edges
int dist[N], cnt[N];        // dist[x] stores the shortest distance from vertex 1 to x, cnt[x] stores the number of vertices passed through from 1 to x on the shortest path
bool st[N];     // Stores whether each vertex is in the queue

// If there exists a negative cycle, returns true; otherwise, returns false.
bool spfa()
{
    // No need to initialize dist array
    // Principle: If there are n vertices on a certain shortest path (excluding oneself), then including oneself, there is a total of n+1 vertices. According to the pigeonhole principle, there must be two identical vertices, therefore a cycle exists.

    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;