P3371 【模板】单源最短路径（弱化版）

P4779 【模板】单源最短路径（标准版）

1. Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool vis[MAXn + 10]; int dis[MAXn + 10];
priority_queue<pair<int, int> > q;
void Dijkstra(int root) {
    memset(dis, 0x3f, sizeof(dis));
    dis[root] = 0;
    q.push(make_pair(0, root));
    while (!q.empty()) {
        int cur = q.top().second; q.pop();
        if (vis[cur]) continue;
        vis[cur] = 1;
        for (re int i = head[cur]; i; i = nex[i]) {
            if (dis[to[i]] > dis[cur] + wei[i]) {
                dis[to[i]] = dis[cur] + wei[i];
                q.push(make_pair(-dis[to[i]], to[i]));
            }
        }
    }
}

Dijkstra(root);

2. SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool inque[MAXn + 10]; int dis[MAXn + 10];
queue<int> q;
void SPFA(int root) {
    memset(dis, 0x3f, sizeof(dis));
    dis[root] = 0;
    q.push(root); inque[root] = 1;
    while (!q.empty()) {
        int cur = q.front(); q.pop(); inque[cur] = 0;
        for (re int i = head[cur]; i; i = nex[i]) {
            if (dis[to[i]] > dis[cur] + wei[i]) {
                dis[to[i]] = dis[cur] + wei[i];
                if (!inque[to[i]]) {
                    q.push(to[i]); inque[to[i]] = 1;
                }
            }
        }
    }
}

SPFA(root);

3. Floyd

1
2
3
4
5
6
7
8
for (re int k = 1; k <= n; ++k) {
    for (re int i = 1; i <= n; ++i) {
        for (re int j = 1; j <= n; ++j) {
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            //传递闭包：con[i][j] |= con[i][k] & con[k][j];
        }
    }
}