最短路

总结

image-20230412204030858

Dijkstra（朴素）

思路：

  1. n次循环，每次找到点集外最近的点
  2. 更新所有点最近距离

AcWing 849. Dijkstra求最短路 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
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int g[N][N],d[N],st[N];
int n,m;

int dj()
{
    memset(d,0x3f,sizeof d);
    d[1]=0;
    
    for(int i=1;i<=n;i++)
    {
        int t=-1;
        //找到集合外最小距离
        for(int j=1;j<=n;j++)
            if(!st[j] && (t==-1 || d[t]>d[j]))t=j;
        st[t]=1;
        //更新所有点
        for(int j=1;j<=n;j++)
            d[j]=min(d[j],d[t]+g[t][j]);
    }
    if(d[n]==0x3f3f3f3f)return -1;
    else return d[n];
}

int main()
{
    memset(g,0x3f,sizeof g);
    
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
    }
    int t=dj();
    cout<<t;
    return 0;
}

Dijkstra（堆优化）

思路：

  1. n次循环，每次找到点集外最近的点（小根堆实现）
  2. 更新所有点最近距离

AcWing 850. Dijkstra求最短路 II

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<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = N * 2;
typedef pair<int, int> PII;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];
int n, m;

void add(int a, int b, int c)
{
    e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx ++;
}

int dj()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0,1});
    while(heap.size())
    {
        PII t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if(st[ver])continue;
        st[ver] = 1;
        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];
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = dj();
    cout << t <<endl;
    return 0;
}

bellman-ford算法

思路

  1. n次循环，循环所有边。
  2. 循环所有边时更新所有边

AcWing 853. 有边数限制的最短路

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
#include<bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e4 + 10;
struct {
    int a, b, w;
} h[M];
int dist[N],backcopy[N];
int n, m ,k;
void bf()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 1; i <= k ; i ++)
    {
        memcpy(backcopy, dist, sizeof backcopy);
        for(int j = 1; j <= m; j ++)
        {
            dist[h[j].b] = min(dist[h[j].b], backcopy[h[j].a] + h[j].w);
        }
    }
    if(dist[n] > 0x3f3f3f3f / 2)puts("impossible");
    else cout << dist[n];
    return;
}
int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i ++)
    {
        cin >> h[i].a >> h[i].b >> h[i].w;
    }
    bf();
    return 0;
}

spfa算法

思路

1
2
3
4
5
6
7
8
queue <- 初点

while（queue不空）
	t <- q.front();
	q.pop();
	// 更新t的所有出边
	t -w-> b 
	(如果b变小了)queue <- b

AcWing 851. spfa求最短路

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];
int n,m;
void add(int a, int b, int c){
    e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx ++;
}
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while(q.size())
    {
        int 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[t])
                {
                    st[j] = true;
                    q.push(j); 
                }
            }
        }
    }
    return dist[n];
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = spfa();
    if(t > 0x3f3f3f3f / 2)cout << "impossible";
    else cout << t;
    return 0;
}

Floyd

思路

1
2
3
4
for(k 1~n)
	for(i 1~n)
		for(j 1~n)
			g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

AcWing 854. 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
#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int g[N][N];
int n, m, t;
void floyd()
{
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
int main()
{
    cin >> n >> m >> t;
    
    memset(g, 0x3f, sizeof g);
    for(int i = 1; i <= n; i ++)g[i][i] = 0;
    
    for(int i = 1; i <= m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    floyd();
    while(t --)
    {
        int a, b;
        cin >> a >> b;
        if(g[a][b] > 1e9 / 2)puts("impossible");
        else cout << g[a][b] << endl;
    }
}