Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

最短路模板

发表于 分类于
本文字数： 9.4k 阅读时长 ≈ 9 分钟
标签：        

用于求解图的最短路问题。

bellman_ford 
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
#include <iostream>
#include <cstdio>
#include <climits>
#define INF INT_MAX
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
int n, m, st, dis[N];
struct edge
{
    int a, b, c;
}k[M];
void bellman_ford()
{
    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    dis[st] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dis[k[j].b] = min(dis[k[j].b], dis[k[j].a] + k[j].c);
}
int main()
{
    int a, b, c;
    cin >> n >> m >> st;
    for (int i = 1; i <= m; i++)
        cin >> k[i].a >> k[i].b >> k[i].c;
    bellman_ford();
    for (int i = 1; i <= n; i++)
        cout << dis[i] << ' ';
    return 0;
}
bellman_ford_with_queue 
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
#include <iostream>
#include <cstdio>
#include <queue>
#include <climits>
#define INF INT_MAX
using namespace std;
const int N = 1e5 + 10, M = 5e5 + 10;
int n, m, st, dis[N];
int wt[M], hd[M], nxt[M], edg[M], idx;
bool vis[N];
void bellman_ford_with_queue()
{
    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    dis[st] = 0;
    queue <int> q;
    q.push(st);
    vis[st] = true;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        vis[t] = false;
        for (int i = hd[t]; i; i = nxt[i])
            if (dis[t] + wt[i] < dis[edg[i]])
            {
                dis[edg[i]] = dis[t] + wt[i];
                if (!vis[edg[i]])
                {
                    q.push(edg[i]);
                    vis[edg[i]] = true;
                }
            }
    }
}
void add(int a, int b, int c)
{
    wt[++idx] = c;
    edg[idx] = b;
    nxt[idx] = hd[a];
    hd[a] = idx;
}
int main()
{
    int a, b, c;
    cin >> n >> m >> st;
    for (int i = 1; i <= m; i++)
    {
        cin >> a >> b >> c;
        add(a, b, c);
    }
    bellman_ford_with_queue();
    for (int i = 1; i <= n; i++)
        cout << dis[i] << ' ';
    return 0;
}
dijkstra 
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
#include <iostream>
#include <cstdio>
#include <climits>
#define INF INT_MAX
using namespace std;
const int N = 1e5 + 10;
int n, m, st, dis[N], path[N][N];
bool vis[N];
void dijkstra()
{
    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    dis[st] = 0;
    for (int i = 1; i <= n; i++)
    {
        int t = 0;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (dis[j] < dis[t] || !t ))
                t = j;
        for (int j = 1; j <= n; j++)
            if (path[t][j] != INF && dis[t] != INF)
                dis[j] = min(dis[j], dis[t] + path[t][j]);
        vis[t] = true;
    }
}
int main()
{
    int a, b, c;
    cin >> n >> m >> st;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            path[i][j] = INF;
    for (int i = 1; i <= m; i++)
    {
        cin >> a >> b >> c;
        path[a][b] = min(path[a][b],c);
    }
    dijkstra();
    for (int i = 1; i <= n; i++)
        cout << dis[i] << ' ';
    return 0;
}
dijkstra_with_heap 
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
#include <iostream>
#include <cstdio>
#include <queue>
#include <climits>
#include <vector>
#include <cstring>
#define INF INT_MAX
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
int st, n, m, dis[N];
int wt[M], edg[M], hd[M], nxt[M], idx;
bool vis[N];
void dijkstra_with_heap()
{
    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    dis[st] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    q.push(make_pair(0, st));
    while (!q.empty())
    {
        pair<int, int> t = q.top();
        q.pop();
        if (vis[t.second])
            continue;
        vis[t.second] = true;
        for (int i = hd[t.second]; i; i = nxt[i])
        {
            int j = edg[i];
            if (dis[j] > t.first + wt[i])
            {
                dis[j] = t.first + wt[i];
                q.push(make_pair(dis[j], j));
            }
        }
    }
}
void add(int a, int b, int c)
{
    edg[++idx] = b;
    wt[idx] = c;
    nxt[idx] = hd[a];
    hd[a] = idx;
}
int main()
{
    int a, b, c;
    cin >> n >> m >> st;
    for (int i = 1; i <= m; i++)
    {
        cin >> a >> b >> c;
        add(a, b, c);
    }
    dijkstra_with_heap();
    for (int i = 1; i <= n; i++)
        cout << dis[i] << ' ';
    return 0;
}
floyd 
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#define INF INT_MAX
using namespace std;
const int N = 1e5 + 10;
int n, m, st, ed, dis[N][N];
void floyd()
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dis[i][k] != INF && dis[k][j] != INF)
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
int main()
{
    int a, b, c;
    cin >> n >> m >> st;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j)
                dis[i][j] = 0;
            else
                dis[i][j] = INF;
    for (int i = 1; i <= m; i++)
    {
        cin >> a >> b >> c;
        dis[a][b] = min(c, dis[a][b]);
    }
    floyd();
    for (int i = 1; i <= n; i++)
        cout << dis[st][i] << ' ';
    return 0;
}
johnson 
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
101
102
103
104
105
106
107
108
109
110
111
112
#include <cstdio>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 3e3 + 10, M = 1e4 + 10, inf = 1e9;
bool vis[N];
int n, m, h[N], dis[N][N], cnt[N];
int idx, hd[N], nxt[M], edg[M], wt[M];
bool spfa(int st, int *d)
{
    for (int i = 1; i <= n; i++)
        d[i] = inf;
    queue<int> q;
    q.push(st);
    vis[st] = true;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        vis[t] = false;
        for (int i = hd[t]; ~i; i = nxt[i])
            if (d[t] + wt[i] < d[edg[i]])
            {
                d[edg[i]] = d[t] + wt[i];
                cnt[edg[i]] = cnt[t] + 1;
                if (cnt[edg[i]] > n)
                    return false;
                if (!vis[edg[i]])
                {
                    vis[edg[i]] = true;
                    q.push(edg[i]);
                }
            }
    }
    return true;
}
void dijkstra(int st, int *d)
{
    for (int i = 1; i <= n; i++)
    {
        vis[i] = false;
        cnt[i] = 0;
        d[i] = inf;
    }
    priority_queue<PII, vector<PII>, greater<PII>> q;
    d[st] = 0;
    q.push(make_pair(0, st));
    while (!q.empty())
    {
        int t = q.top().second;
        q.pop();
        if (vis[t])
            continue;
        vis[t] = true;
        for (int i = hd[t]; ~i; i = nxt[i])
            if (d[t] + wt[i] < d[edg[i]])
            {
                d[edg[i]] = d[t] + wt[i];
                q.push(make_pair(d[edg[i]], edg[i]));
            }
    }
    for (int i = 1; i <= n; i++)
        d[i] < inf && (d[i] += h[i] - h[st]);
}
void add(int a, int b, int c)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
    wt[idx] = c;
}
int main()
{
    read(n), read(m);
    for (int i = 0; i <= n; i++)
        hd[i] = -1;
    for (int u, v, w; m; m--)
    {
        read(u), read(v), read(w);
        add(u, v, w);
    }
    for (int i = 1; i <= n; i++)
        add(0, i, 0);
    if (!spfa(0, h))
        return puts("-1"), 0;
    for (int i = 1; i <= n; i++)
        for (int j = hd[i]; ~j; j = nxt[j])
            wt[j] += h[i] - h[edg[j]];
    for (int i = 1; i <= n; i++)
        dijkstra(i, dis[i]);
    return 0;
}

Which to choose

  • Single-Source without cycle of minus length: dijkstrea_with_heap;
  • Single-Source with cycle of minus length: bellman_ford_with_queue;
  • Single-Source with cycle of minus length and limit on the number of edges: bellman_ford
  • Multi-source: floyd, johnson
相关文章