HDU_1874_SPFA模板

原理：

  • 在有向图中,对于某个边(u,v,w),若存在dist[v] < dist[u]+w,满足三角关系，
  • 若所有边都满足此不等式,说明一个点已经无法通过任意联通点来松弛它,则所有的dist就是最短路

来源：

  • 与 dij不同的是,bellman-ford基于迭代思想
  • spfa是队列优化的bellman-ford

流程：

  1. 将源点加入队列,
  2. 取出队头,扫描所有出边(u,v,w),松弛:dist[v] > dist[u] + w,若v点不在队列中,加入队列
  3. 队列中保存了待扩展的节点，每一次节点的入队都更新了一次dist数组,一个点可能多次入队,不断的迭代

邻接表：

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
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>

using namespace std;
const int maxn = 1e3;
const int INF = 0x3f3f3f3f;

queue<int> que;
bool vis[maxn];
int dist[maxn];
int n,m;
vector<pair<int,int> > e[maxn];

void spfa() {
	memset(dist,0x3f,sizeof dist);
	memset(vis,0,sizeof vis);

	dist[1] = 0; vis[1] = 1;
	que.push(1);

	while (!que.empty()) {
		int cur = que.front(); que.pop();
		vis[cur] = 0;
		for (int i=0; i<e[cur].size(); i++) {
			int to = e[cur][i].first;
			int div = e[cur][i].second;
			if (dist[to] > dist[cur] + div) {
				dist[to] = dist[cur] + div;
				if (!vis[to]) vis[to] = 1,que.push(to);
			}
		}
	}
	return ;
}

void read() {
	memset(e,0x3f,sizeof e);
	scanf("%d%d",&n,&m);
	for (int i=1; i<=m ;i++) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e[u].push_back( make_pair(v,w) );
	}
}

int main() {
	read();
	spfa();
	return 0;
}

邻接矩阵 HDU 1874 

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
#include <iostream>
#include <string.h>
#include <queue>

using namespace std;
const int maxn = 201;
const int INF = 0x3f3f3f3f;
int e[maxn][maxn];
int startp,endp;
bool vis[maxn];
int dist[maxn];
int n,m;

int spfa() {
	memset(vis,0,sizeof vis);
	memset(dist,0x3f,sizeof dist);

	dist[startp] = 0; vis[startp] = 1;
	queue<int> que;
	que.push(startp);

	while (!que.empty()) {
		int cur = que.front(); que.pop();
		vis[cur] = 0;
		for (int i=0; i<n; i++) {
			if (e[cur][i] < INF && dist[i] > dist[cur] + e[cur][i]) {
				dist[i] = dist[cur] + e[cur][i];
				if (!vis[i]) que.push(i),vis[i] = 1;
			}
		}
	}
	return dist[endp];
}
int main() {
//	freopen("a.txt","r",stdin);
	while (scanf("%d%d",&n,&m) != EOF) {
		memset(e,0x3f,sizeof e);
		for (int i =1; i<=m; i++) {
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			if (w < e[u][v]) e[u][v] = e[v][u] = w;
		}
		scanf("%d%d",&startp,&endp);
		int ans = spfa();
		if (ans < INF) printf("%d\n",ans);
		else printf("-1\n");
	}
	return 0;
}
算法
spfa

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！