Criska

spfa最短路

• 分类: spfa, 最短路 • 标签: spfa, 最短路

spfa模板

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<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
const int N=200000;
int n,m,head[N],tope,x,y,z,st,ed;
int dis[N],in[N];
struct node{
	int to,next,w;
}e[N];
queue<int>q;
int intt(int x,int y,int z)
{
	tope++;
	e[tope].next=head[x];
	e[tope].to=y;
	e[tope].w=z;
	head[x]=tope;
}
int spfa(int x)
{
	int ce;
	for(int i=1;i<=n;++i)
		dis[i]=99999999999;
	q.push(x); dis[x]=0; in[x]=1;
	do
	{
		ce=q.front();
		q.pop();
		in[ce]=0;
		for(int i=head[ce];i;i=e[i].next)
		{
			if(dis[ce]+e[i].w<dis[e[i].to])
			{
				dis[e[i].to]=dis[ce]+e[i].w;
				if(in[e[i].to]==0)
				{
					q.push(e[i].to);
					in[e[i].to]=1;
				}
			}
		}
	}while(!q.empty());
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		intt(x,y,z);
	}
	scanf("%d%d",&st,&ed);
	spfa(st);
	printf("%d",dis[ed]);
	return 0;
}

附上一道SYZOJ的最短路裸题

最短路

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
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
const int N=100100;
int n,m,head[N],tope,x,y,z;
int in[N],dis[N];
struct node{
	int to,next;
	int w;
}e[N];
int intt(int x,int y,int z)
{
	tope++;
	e[tope].next=head[x];
	e[tope].to=y;
	e[tope].w=z;
	head[x]=tope;	
}
queue<int>q;
int spfa(int x)
{
	int ce;
	for(int i=1;i<=n;++i)
		dis[i]=99999999;
	dis[x]=0; q.push(x); in[x]=1;
	do
	{
		ce=q.front();
		in[ce]=0;
		q.pop();
		for(int i=head[ce];i;i=e[i].next)
		{
			if(dis[ce]+e[i].w<dis[e[i].to])
			{
				dis[e[i].to]=dis[ce]+e[i].w;
				if(in[e[i].to]==0)
				{
					q.push(e[i].to);
					in[e[i].to]=1;
				}
			}
		}
		
	}while(!q.empty());
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		intt(x,y,z);
	}
	spfa(1);
	printf("%d",dis[n]);
	return 0;
}

最短路计数

这道题的意思就是记录从1到n个点的最短路长度，所以只要在spfa的过程中加一个路径的记录值就可以了。
代码如下：

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
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=2000000;
int n,m,tope,head[N],cnt[N];
int dis[N],in[N];
queue<int>q;
struct node{
	int to,next,w;
}e[N];
int intt(int x,int y,int z)
{
	tope++;
	e[tope].next=head[x];
	e[tope].to=y;
	e[tope].w=z;
	head[x]=tope;
}
int spfa(int x)
{
	int ce;
	cnt[x]=1;
	for(int i=1;i<=n;++i)
		dis[i]=999999999;
	dis[x]=0; in[x]=1; q.push(x);
	do
	{
		ce=q.front();
		in[ce]=0;
		q.pop();
		for(int i=head[ce];i;i=e[i].next)
		{
			if(dis[ce]+e[i].w<dis[e[i].to])
			{
				dis[e[i].to]=dis[ce]+e[i].w;
				cnt[e[i].to]=cnt[ce]%100003;//如果可以更新最短路，那么指向的点的路径值等于它的前一个点
				if(in[e[i].to]==0)
				{
					in[e[i].to]=1;
					q.push(e[i].to);
					
				}
			}
			else
				if(dis[ce]+e[i].w==dis[e[i].to])
					cnt[e[i].to]=(cnt[e[i].to]+cnt[ce])%100003;//如果有相同的最短路，那么增加这条路上的路径值
			
		}
	} while(!q.empty());
}
int main()
{
	scanf("%d%d",&n,&m);
	int a,b,st,ed;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&a,&b);
		intt(a,b,1);
		intt(b,a,1);
	}
	spfa(1);
	for(int i=1;i<=n;++i)
	{
		if(dis[i]==999999999) printf("%d\n",0);
		else printf("%d\n",cnt[i]);
	}
	return 0;
}

Motor（复制K层图求最短路）

Description

在你的强力援助下，PCY成功完成了之前的所有任务，他觉得，现在正是出去浪的大好时光。 于是，他来到高速公路上，找到一辆摩的前往几千公里以外他心仪的那家黄焖鸡米饭。 由于PCY 的品味异于常人，途经几百个城市的黄焖鸡米饭他都不屑一顾，他只愿意前往他心中最好的那家，但是为了一碗二十块钱的黄焖鸡米饭，他不愿意花上几千块的路费，他希望路费尽量少。高速路上的警察叔叔被他的行为所打动，于是在多方协调下，最多 K 条城市之间的高速收费站愿意免费为 PCY 放行（可以任意选择）。
显然，PCY已经筋疲力尽，不想再动用自己的数学天才来计算他可以花费的最小路费，因此他希望你可以帮他最后一次，他说他可以请你吃大碗的黄焖鸡米饭，还可以加一瓶豆奶。 现在给你N 个城市（编号为 0 … N - 1），M 条道路，和每条高速公路的花费 Wi，以及题目所描述的 K。PCY 想从城市 S 到城市T，因为他对T 城市的黄焖鸡米饭情有独钟。

Input (Prefix.in)

第一行，三个整数N，M，K，如题意所描述
第二行，两个整数S，T，代表出发城市和目标城市编号
接下来M 行，每行三个整数 X，Y，W，代表X 和 Y 城市之间的高速公路收费为 W 元

Output (Prefix.out)

共一行，输出一个整数，代表 PCY 最少需要花费的路费。

Sample Input
【1】
5 6 1
0 4
2 3 5
0 1 15
1 2 5
3 4 5
2 3 3
0 2 1005

【2】
3 3 1
1 3
0 1 50
1 2 30
1 3 50

Sample Output
【1】
8

【2】
0

Explanation

自己动手，丰衣足食

Hint

对于10%的数据，N <= 100，K = 0
对于30%的数据，N <= 5，M <= 10，K <= 2
对于100%的数据，N <= 10000，M <= 50000，K <= 10，Wi <= 10000

内存限制256M，时间限制 1s

  • 分层图+SPFA。我们把整个图分为 K 层，每一层之间是原图的连接关系，而对于一条边 x <-> y 我们会连两条单向边 x -> y’，y -> x’ ，这样一旦到了下一层就无法回到上一层了。最后的答案为最后一层的ed的最短路。 
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
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=600000;
int n,m,k,tope,head[N*4],st,ed;
int dis[N*4],in[N*4];
queue<int>q;
struct node{
	int to,next,w;
}e[N*4];
inline void intt(int x,int y,int z)
{
	tope++;
	e[tope].to=y;
	e[tope].w=z;
	e[tope].next=head[x];
	head[x]=tope;
}
inline void spfa(int x)
{
	for(int i=1;i<=n*(k+1);++i)
		dis[i]=99999999;
	dis[x]=0;in[x]=1;q.push(x);
	do
	{
		int ce;
		ce=q.front();
		in[ce]=0;
		q.pop();
		for(int i=head[ce];i;i=e[i].next)
		{
			if(dis[ce]+e[i].w<dis[e[i].to])
			{
				dis[e[i].to]=dis[ce]+e[i].w;
				if(in[e[i].to]==0)
				{
					in[e[i].to]=1;
					q.push(e[i].to);
				}
			}
		}
	}while(!q.empty());
}
int main()
{
	freopen("Motor.in","r",stdin);
	freopen("Motor.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	scanf("%d%d",&st,&ed);
	for(int i=1;i<=m;++i)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		intt(x,y,z);
		intt(y,x,z);
		for(int j=1;j<=k;++j)
		{
			intt(x+n*j,y+n*j,z);
			intt(y+n*j,x+n*j,z);
			intt(x+n*(j-1),y+n*j,0);
			intt(y+n*(j-1),x+n*j,0);
		}
	}
	spfa(st);
	printf("%d",dis[ed+n*k]);
	return 0;
}