邻接矩阵存储

适用情况：稠密图，即边数 E 接近顶点数 V 的平方时，空间利用率高。

时间复杂度：O(n2)O(n^2)

空间复杂度：O(n2)O(n^2)

邻接矩阵存储写法

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
#include <bits/stdc++.h>
using namespace std;

const int N = 510;

int n, m, x, y, z;
int a[N][N], dis[N];

bool vis[N];

int dijkstra()
{
	//因为要找最近的点，所以所有点距离1点距离初始化为极大值
	memset(dis, 0x3f, sizeof dis);
	//标记第一个点距离1号点距离为0
	dis[1] = 0;
	//vis[1] = true加上这行第一次循环就标记不出t
	
	for (int i = 1; i <= n; i++)
	{
		//寻找未访问的最近点
		int t = -1;
		for (int j = 1; j <= n; j++)
			if (!vis[j] && (t == -1 || dis[j] < dis[t]))
				t = j;
		//标记最近点t
		vis[t] = true;
		//用最近点t更新未被标记过的点
		for (int j = 1; j <= n; j++)
			if (!vis[j])
                //如果t到j走不通，那就是极大值，不会影响最短距离计算
				dis[j] = min(dis[j], dis[t] + a[t][j]);
	}
	//无法从1号点走到n号点
	if (dis[n] == 0x3f3f3f3f)
		return -1;
	else
		return dis[n];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	//邻接矩阵初始化为极大值
	memset(a, 0x3f, sizeof a);
	
	cin >> n >> m;
	while (m--)
	{
		cin >> x >> y >> z;
		//防止重边，取最小值
		a[x][y] = min(a[x][y], z);
	}
	
	int ans = dijkstra();
	
	cout << ans << endl;
	
	return 0;
}

用邻接表矩阵来写也是可以的，空间复杂度O(n+m)O(n + m)，但是需要注意数据范围，写法如下

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, x, y, z, idx;
int h[N], ed[N], nxt[N],  val[N], dis[N];
bool vis[N];

void add(int a, int b, int c)
{
	ed[idx] = b;
	val[idx] = c;
	nxt[idx] = h[a];
	h[a] = idx++;
}

int dijkstra()
{
	memset(dis, 0x3f, sizeof dis);
	dis[1] = 0;
	
	for (int i = 1; i <= n; i++)
	{
		int t = -1;
		for (int j = 1; j <= n; j++)
			if (!vis[j] && (t == -1 || dis[j] < dis[t]))
				t = j;
		vis[t] = true;
		//遍历t能到达的所有点，其余的保留原值即可(不用遍历到)
		for (int j = h[t]; j != -1; j = nxt[j])
		{
			int v = val[j]; //边的权重
			int p = ed[j];//邻居节点
			if (!vis[p])
				dis[p] = min(dis[p], dis[t] + v);
		}
	}
	if (dis[n] == 0x3f3f3f3f)
		return -1;
	else
		return dis[n];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	memset(h, -1, sizeof h);
	
	cin >> n >> m;
	while (m--)
	{
		cin >> x >> y >> z;
		add(x, y, z);
	}
	
	int ans = dijkstra();
	
	cout << ans << endl;
	
	return 0;
}

邻接表存储

适用场景：稀疏图，即边数 E 远小于 V² 时，这是最常见的情况

时间复杂度：

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

typedef pair<int, int> PII;

priority_queue<PII, vector<PII>, greater<PII>>q;

int n, m, x, y, z, idx;
int h[N], ed[N], nxt[N], w[N], dis[N];
bool vis[N];


void add(int x, int y, int z)
{
	ed[idx] = y;
	w[idx] = z;
	nxt[idx] = h[x];
	h[x] = idx++;
}

int dijkstra()
{
	memset(dis, 0x3f, sizeof dis);
	dis[1] = 0;
	//距离 点号
	q.push({0, 1});
	while (!q.empty())
	//当发现到某个节点的更短路径时，我们会重新将该节点加入队列
	//，不同于数组的更新，所以不能用n次循环来代替!q.empty()
	{
		auto t = q.top();
		q.pop();
		int distance = t.first, p = t.second;
		//同一个点在没被标记（最短路）之前可能由别的节点扩展，写上这行避免重复处理同一个点(效率较高)
		if (vis[p])
			continue;
		vis[p] =true;//p这个点的距离已经是最优，标记上
		for (int j = h[p]; j != -1; j = nxt[j])
		{
			int px = ed[j];
			int wx = w[j];
			if (dis[px] > distance + wx)
			{
				dis[px] = distance + wx;
				q.push({dis[px], px});
			}
		}
		
	}
	if (dis[n] == 0x3f3f3f3f)
		return -1;
	return dis[n];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	memset(h, -1, sizeof h);
	
	cin >> n >> m;
	while (m--)
	{
		cin >> x >> y >> z;
		add(x, y, z);
	}
	
	int ans = dijkstra();
	
	cout << ans << endl;
	
	return 0;
}

//1.0463 s
//0.8308 s