题解 | #【模板】单源最短路1#

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
using namespace std;

//采用spfa算法

const int N = 5010, M = 10e5 + 10;
int h[N], e[M], ne[M], idx, n, m;
int dist[N], que[N], hh, tt;

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

int spfa() {
	dist[1] = 0;
	que[tt++] = 1;
	while (hh <= tt) {
		int t = que[hh++];	//取出队头元素
		for (int i = h[t];i != -1;i = ne[i]) {
			int j = e[i];
			if (dist[j] > dist[t] + 1) {
				dist[j] = dist[t] + 1;
				que[tt++] = j;
			}
		}
	}
	if (dist[n] == 0x3f3f3f3f)
		return -1;
	else
		return dist[n];
}


int main() {
	memset(h, -1, sizeof h);
	memset(dist, 0x3f, sizeof dist);
	cin >> n >> m;
	while (m--) {
		int u, v;
		cin >> u >> v;
		if (u == v)
			continue;
		add(u, v), add(v, u);
	}
	int t = spfa();
	if (t == 0x3f3f3f3f)
		printf("-1\n");
	else
		printf("%d\n", t);
	return 0;
}

由于本题不存在负环边，可以采用spfa算法，时间复杂度为 O(m).

spfa算法对bellmen_ford算法进行了优化，其基本思路是：

定义队列存储等待用于更新dist[i]的顶点，每一次都从队列中选取出一个顶点v,用以更新起点到达v的邻接点的最短距离。倘若u为v的邻接点，当dist[u]>dist[v]+1时，dist[u] = dist[v]+1,并且u加入队列。对于满足dist[u]==dist[v]+1的顶点u,由于无需考虑将u加入到队列。