[最短路] 学习笔记

Zwjay's Blog / 2023-08-09 / 原文

建图

邻接矩阵

时间、空间：\(O(n^2)\)

int n, m, e[N][N];
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i ++)
	{
		int x, y, w;
		cin >> x >> y >> w;
		e[x][y] = w;
		e[y][x] = w;
	}
	for (int i = 1; i <= n; i ++)
	{
		for (int j = 1; j <= n; j ++) cout << e[x][y] << ' ';
		cout << '\n';
	}		
}

边集数组

时间：\(O(nm)\) ，空间：\(O(m)\)

struct edge
{
	int x, y, w;
}e[2*M];
int n, m;
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i ++)
	{
		int x, y, w;
		cin >> x >> y >> w;
		e[i] = {x, y, w};
		e[i+m] = {y, x, w};
	}
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m << 1; j ++)
			if (e[j].x == i)  
				printf("%d %d %d\n", i, e[j].y, e[j].w);
}

邻接表（vector）

时间、空间：\(O(n+m)\) （不开 \(O2\) 时要注意 vector 常数大）

struct edge
{
	int y, w;
};
vector<edge> e[N];
int n, m;
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i ++)
	{
		int x, y, w;
		cin >> x >> y >> w;
		e[x].push_back({y, w});
		e[y].push_back({x, w});
	}
	for (int i = 1; i <= n; i ++)
		for (int j = 0; j < e[i].size(); j ++)
			printf("%d %d %d\n", i, e[i][j].y, e[i][j].w);		
}

链式前向星

这个视频讲得很好

时间、空间：\(O(n+m)\)

struct edge
{
	int to, w, next;
}e[M];
int n, m, top, h[N];
void add(int x, int y, int w)
{
	e[++top] = {y, w, h[x]};
	h[x] = top;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i ++)
	{
		int x, y, w;
		cin >> x >> y >> w;
		add(x, y, w);
		add(y, x, w);
	}
	for (int i = 1 i <= n; i ++) 
		for (int j = h[i]; ~j; j = e[j].next)
			printf("%d %d %d\n", i, e[j].to, e[j].w);
		
}