Modèle De Base D'algorithme

 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) {/* ... */} // Vérifie si x satisfait une certaine propriété

// Utilisé lorsque l'intervalle [l, r] est divisé en [l, mid] et [mid + 1, r] :
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check() vérifie si mid satisfait la propriété
        else l = mid + 1;
    }
    return l;
}
// Utilisé lorsque l'intervalle [l, r] est divisé en [l, mid - 1] et [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) {/* ... */} // Vérifie si x satisfait une certaine propriété

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps représente la précision, dépend des exigences de précision du problème
    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, satisfait 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] = Somme de tous les éléments dans la partie supérieure gauche de la case i, j
La somme de la sous-matrice ayant pour coin supérieur gauche (x1, y1) et pour coin inférieur droit (x2, y2) est :
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

1
2

Ajouter c à tous les éléments de la sous-matrice ayant pour coin supérieur gauche (x1, y1) et pour coin inférieur droit (x2, y2) :
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

1
2

Trouver le k-ième chiffre de n : n >> k & 1
Retourner le dernier 1 de 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 ++ ;

    // Logique spécifique au problème
}
Classification des problèmes courants :
    (1) Pour une séquence, utiliser deux pointeurs pour maintenir un intervalle
    (2) Pour deux séquences, maintenir un certain ordre, par exemple l'opération de fusion de deux séquences triées dans le tri par fusion

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

vector<int> alls; // Stocker toutes les valeurs à discrétiser
sort(alls.begin(), alls.end()); // Trier toutes les valeurs
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // Supprimer les éléments dupliqués

// Recherche binaire pour trouver la valeur discrétisée de x
int find(int x) // Trouver la première position supérieure ou égale à 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; // Mappé à 1, 2, ...n
}

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

// Fusionner tous les intervalles qui se chevauchent
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 stocke la tête de la liste chaînée, e[] stocke les valeurs des nœuds, ne[] stocke les pointeurs next des nœuds, idx indique quel nœud est actuellement utilisé
int head, e[N], ne[N], idx;

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

// Insérer un nombre a en tête de la liste chaînée
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// Supprimer le nœud de tête, il faut s'assurer que le nœud de tête existe
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[] représente la valeur des nœuds, l[] représente le pointeur gauche des nœuds, r[] représente le pointeur droit des nœuds, idx indique quel nœud est actuellement utilisé
int e[N], l[N], r[N], idx;

// Initialisation
void init()
{
    //0 est le point d'extrémité gauche, 1 est le point d'extrémité droit
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// Insérer un nombre x à droite du nœud a
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// Supprimer le nœud 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 représente le sommet de la pile
int stk[N], tt = 0;

// Insérer un nombre au sommet de la pile
stk[ ++ tt] = x;

// Retirer un nombre du sommet de la pile
tt -- ;

// Valeur au sommet de la pile
stk[tt];

// Vérifier si la pile est vide, si tt > 0, alors elle n'est pas vide
if (tt > 0)
{

}

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

// hh représente la tête de la file d'attente, tt représente la queue de la file d'attente
int q[N], hh = 0, tt = -1;

// Insérer un nombre à la queue de la file d'attente
q[ ++ tt] = x;

// Retirer un nombre de la tête de la file d'attente
hh ++ ;

// Valeur à la tête de la file d'attente
q[hh];

// Vérifier si la file d'attente est vide, si hh <= tt, alors elle n'est pas vide
if (hh <= tt)
{
}

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

// hh représente la tête de la file d'attente, tt représente la position après la queue de la file d'attente
int q[N], hh = 0, tt = 0;

// Insérer un nombre à la queue de la file d'attente
q[tt ++ ] = x;
if (tt == N) tt = 0;

// Retirer un nombre de la tête de la file d'attente
hh ++ ;
if (hh == N) hh = 0;

// Valeur à la tête de la file d'attente
q[hh];

// Vérifier si la file d'attente est vide, si hh != tt, alors elle n'est pas vide
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 ++ ;  // Vérifier si la tête de file est hors de la fenêtre
    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[] est le texte long, p[] est la chaîne modèle, n est la longueur de s, m est la longueur de p
Calculer le tableau Next de la chaîne modèle :
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;
}

// Appariement
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];
        // Logique après un appariement réussi
    }
}// La fonction de bibliothèque C strstr() est ainsi

 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;
// Le point 0 est à la fois le nœud racine et le nœud vide
// son[][] stocke les fils de chaque nœud de l'arbre
// cnt[] stocke le nombre de mots se terminant à chaque nœud

// Insérer une chaîne
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] ++ ;
}

// Rechercher le nombre d'occurrences d'une chaîne
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];
}// On peut utiliser map<string,int>, mais le temps est plus de deux fois supérieur

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

    int p[N]; // Stocke le nœud ancêtre de chaque point

    // Retourne le nœud ancêtre de x
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // Initialisation, supposons que les numéros de nœud sont de 1 à n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // Fusionner les deux ensembles contenant a et b :
    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[] stocke le nœud ancêtre de chaque point, size[] n'a de sens que pour les nœuds ancêtres, indique le nombre de points dans l'ensemble du nœud ancêtre

    // Retourne le nœud ancêtre de x
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // Initialisation, supposons que les numéros de nœud sont de 1 à n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // Fusionner les deux ensembles contenant a et b :
    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[] stocke le nœud ancêtre de chaque point, d[x] stocke la distance de x à p[x]

    // Retourne le nœud ancêtre de 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];
    }

    // Initialisation, supposons que les numéros de nœud sont de 1 à n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // Fusionner les deux ensembles contenant a et b :
    p[find(a)] = find(b);
    d[find(a)] = distance; // Selon le problème spécifique, initialiser le décalage de 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] stocke les valeurs dans le tas, h[1] est le sommet du tas, le fils gauche de x est 2x, le fils droit est 2x + 1
// ph[k] stocke la position dans le tas du k-ième point inséré
// hp[k] stocke le k-ième point dans le tas est le k-ième inséré
int h[N], ph[N], hp[N], size;

// Échanger deux points et leur relation de mappage
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) construction de tas
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) Méthode des chaînes
    int h[N], e[N], ne[N], idx;

    // Insérer un nombre dans la table de hachage
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // Rechercher si un nombre existe dans la table de hachage
    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) Méthode de recherche ouverte
    int h[N];

    // Si x est dans la table de hachage, retourne l'indice de x ; si x n'est pas dans la table de hachage, retourne la position où x devrait être inséré
    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] stocke la valeur de hachage des k premiers caractères de la chaîne, p[k] stocke P^k mod 2^64

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

// Calculer la valeur de hachage de la sous-chaîne 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, tableau de longueur variable, idée de doublement
    size()  Retourne le nombre d'éléments
    empty()  Retourne si c'est vide
    clear()  Effacer
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    Supporte les opérations de comparaison, par ordre lexicographique

pair<int, int>
    first, Premier élément
    second, Deuxième élément
    Supporte les opérations de comparaison, avec first comme premier critère, second comme deuxième critère (ordre lexicographique)

string, chaîne de caractères
    size()/length()  Retourne la longueur de la chaîne
    empty()
    clear()
    substr(indice de départ, (longueur de la sous-chaîne))  Retourne la sous-chaîne
    c_str()  Retourne l'adresse de début du tableau de caractères où se trouve la chaîne

queue, file d'attente
    size()
    empty()
    push()  Insérer un élément à la queue
    front()  Retourne l'élément en tête
    back()  Retourne l'élément en queue
    pop()  Retirer l'élément en tête

priority_queue, file d'attente prioritaire, par défaut c'est un tas max
    size()
    empty()
    push()  Insérer un élément
    top()  Retourne l'élément au sommet du tas
    pop()  Retirer l'élément au sommet du tas
    Définir comme un tas min : priority_queue<int, vector<int>, greater<int>> q;

stack, pile
    size()
    empty()
    push()  Insérer un élément au sommet
    top()  Retourne l'élément au sommet
    pop()  Retirer l'élément au sommet

deque, file d'attente double
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, basé sur un arbre binaire équilibré (arbre rouge-noir), maintient dynamiquement une séquence ordonnée
    size()
    empty()
    clear()
    begin()/end()
    ++, -- Retourne le prédécesseur et le successeur, complexité temporelle O(logn)

    set/multiset
        insert()  Insérer un nombre
        find()  Rechercher un nombre
        count()  Retourne le nombre d'occurrences d'un nombre
        erase()
            (1) L'entrée est un nombre x, supprime tous les x   O(k + logn)
            (2) L'entrée est un itérateur, supprime cet itérateur
        lower_bound()/upper_bound()
            lower_bound(x)  Retourne l'itérateur du plus petit nombre supérieur ou égal à x
            upper_bound(x)  Retourne l'itérateur du plus petit nombre supérieur à x
    map/multimap
        insert()  L'élément inséré est une paire
        erase()  L'entrée est une paire ou un itérateur
        find()
        []  Attention, multimap ne supporte pas cette opération. La complexité temporelle est O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, table de hachage
    Similaire à ce qui précède, la complexité temporelle pour ajouter, supprimer, modifier et rechercher est O(1)
    Ne supporte pas lower_bound()/upper_bound(), ++, -- pour les itérateurs

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

    count()  Retourne le nombre de 1

    any()  Vérifie s'il y a au moins un 1
    none()  Vérifie si tout est 0

    set()  Mettre tous les bits à 1
    set(k, v)  Mettre le k-ième bit à v
    reset()  Mettre tous les bits à 0
    flip()  Équivalent à ~
    flip(k) Inverser le k-ième bit

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

// Pour chaque point k, ouvrir une liste chaînée simple, stocker tous les points atteignables à partir de k. h[k] stocke le nœud de tête de cette liste chaînée
int h[N], e[N], ne[N], idx;

// Ajouter une arête a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// Initialisation
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] représente que le point u a déjà été parcouru

    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; // Représente que le point 1 a déjà été parcouru
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; // Représente que le point j a déjà été parcouru
            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] stocke le degré entrant du 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;
        }
    }

    // Si tous les points ont été ajoutés à la file, cela signifie qu'il existe une séquence topologique ; sinon, il n'en existe pas.
    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];  // Stocke chaque arête
int dist[N];  // Stocke la distance la plus courte du point 1 à chaque point
bool st[N];   // Stocke si la distance la plus courte de chaque point a déjà été déterminée

// Calculer la distance la plus courte du point 1 au point n, si elle n'existe pas, retourner -1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // Parmi les points dont la distance la plus courte n'est pas encore déterminée, trouver celui avec la plus petite distance
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // Utiliser t pour mettre à jour la distance des autres 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;      // Nombre de points
int h[N], w[N], e[N], ne[N], idx;       // Liste d'adjacence stockant toutes les arêtes
int dist[N];        // Stocke la distance de tous les points au point 1
bool st[N];     // Stocke si la distance la plus courte de chaque point a déjà été déterminée

// Calculer la distance la plus courte du point 1 au point n, si elle n'existe pas, retourner -1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first stocke la distance, second stocke le numéro du point

    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 représente le nombre de points, m représente le nombre d'arêtes
int dist[N];        // dist[x] stocke la distance la plus courte de 1 à x

struct Edge     // Arête, a représente le point de départ, b représente le point d'arrivée, w représente le poids de l'arête
{
    int a, b, w;
}edges[M];

// Calculer la distance la plus courte de 1 à n, si elle n'existe pas, retourner -1.
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // Si la n-ième itération continue de relâcher l'inégalité triangulaire, cela signifie qu'il existe un chemin de longueur n+1, selon le principe des tiroirs, il y a au moins deux points identiques sur le chemin, indiquant qu'il existe un cycle de poids négatif dans le graphe.
    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;      // Nombre total de points
int h[N], w[N], e[N], ne[N], idx;       // Liste d'adjacence stockant toutes les arêtes
int dist[N];        // Stocke la distance la plus courte de chaque point au point 1
bool st[N];     // Stocke si chaque point est dans la file d'attente

// Calculer la distance la plus courte du point 1 au point n, si elle n'existe pas, retourner -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])     // Si j est déjà dans la file d'attente, ne pas l'insérer à nouveau
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

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