【模板】单源最短路径(弱化版) 洛谷P3371

题目链接洛谷P3371

[kuangbin带你飞]专题六最短路

题目描述

题目描述
如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。

输入输出格式
输入格式:
第一行包含三个整数N、M、S,分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi,分别表示第i条有向边的出发点、目标点和长度。

输出格式:
一行,包含N个用空格分隔的整数,其中第i个整数表示从点S出发到点i的最短路径长度(若S=i则最短路径长度为0,若从点S无法到达点i,则最短路径长度为2147483647)


思路

Dijkstra算法:
Dijkstra算法和Prim算法的思想类似都是贪心的思想,不断加入最短的边,直到联通所有的顶点即可;

该题如果直接利用Dijkstar会超内存。即如果利用邻接矩阵存图的话,需要存储10000 * 10000 个对应关系,这使得我们必须优化内存来通过此题;

再此题中,我选择应用链式前向星来存图,可以节省内存开销;
链式前向星存图学习:大佬的链式前向星 图文并茂的
建议大家手绘一下,模拟整个存图过程的实现,易于理解;

我的理解是:邻接矩阵是存储顶点到顶点的关系,这就有许多没用的关系也进行了存储;而链式前向星是用来存储边的集合,所以大家可以依据题目要求选择适当的结构来存储; 链式前向星可以自己过滤掉重边,因为他在寻找i为起点的所有路径,自然会选择最短的;(事实上,它也存储了那些权值较大的边,只是在Dijkstra算法的过程中,会选择权值最小的边)


代码 未使用前向星(只过了70%的数据):

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAX 10010
#define INF 0x3f3f3f3f

int mat[MAX][MAX], vis[MAX], dist[MAX];

void init(int n)
{
memset(vis, 0, sizeof(vis));
for(int i = 1; i<=n; i++)
{
for(int j = 1; j<=n; j++)
mat[i][j] = INF;
dist[i] = INF;
}
}

void Union(int x, int y, int val)
{
if(val < mat[x][y])
mat[x][y] = val;
}

void Dijkstra(int n, int v)
{
dist[v] = 0;
for(int i = 0; i<n; i++)
{
int min_vertex, min_dist = INF;
for(int j = 1; j<=n; j++)
{
if(!vis[j] && dist[j] < min_dist)
{
min_dist = dist[j];
min_vertex = j;
}
}
vis[min_vertex] = 1;
for(int j = 1; j<=n; j++)
{
if(!vis[j] && mat[min_vertex][j] + min_dist < dist[j])
{
dist[j] = mat[min_vertex][j] + min_dist;
}
}
}
}

int main()
{
int n, m, v;
cin >> n >> m >> v;
init(n);
for(int i = 0; i<m; i++)
{
int x, y, val;
cin >> x >> y >> val;
Union(x, y, val);
}
Dijkstra(n, v);
for(int i = 1; i<=n; i++)
{
if(dist[i] == INF)
cout << "2147483647";
else
cout << dist[i];
if(i != n)
cout << " ";
}
return 0;
}

链式前向星优化内存的Dijkstra,可以AC;

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

#include <bits/stdc++.h>
using namespace std;

#define MAXN 500050//边的个数
#define MAX 10010//顶点的个数
#define INF 0x3f3f3f3f

struct Node{
int to;//代表当前边的终点
int next;//代表下一个与当前同起点的下标
int val;//代表当前起点到当前点的权值
}edge[MAXN];

int cnt = 0, vis[MAX], dist[MAX], head[MAXN];

inline void init(int n)
{
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
for(int i = 1; i<=n; i++)
{
dist[i] = INF;
}
}

inline void add(int x, int v, int val)
{
edge[cnt].val = val;
edge[cnt].to = v;
edge[cnt].next = head[x];
head[x] = cnt++;
}

void Dijkstra(int n, int v)
{
dist[v] = 0;
for(int i = 1; i<=n; i++)
{
int min_vertex, min_dist = INF;
for(int j = 1; j<=n; j++)
{
if(!vis[j] && min_dist > dist[j])
{
min_dist = dist[j];
min_vertex = j;
}
}
vis[min_vertex] = 1;
for(int j = head[min_vertex], k = edge[j].to; j != -1; j = edge[j].next, k = edge[j].to)
{
if(!vis[k] && edge[j].val + min_dist < dist[k])
{
dist[k] = edge[j].val + min_dist;
}
}
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, t;
cin >> n >> m >> t;
init(n);
for(int i = 0; i<m; i++)
{
int x, y, val;
cin >> x >> y >> val;
add(x, y, val);
}
Dijkstra(n, t);
for(int i = 1; i<=n; i++)
{
dist[i] == INF ? cout << "2147483647" : cout << dist[i];
if(i != n)
cout << " ";
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------