POJ 3255 Roadblocks 次短路模板 spfa

缘起

【1】中使用了dijkstra的姿势切了次短路的模板题~ 现在再使用spfa的姿势切一次~ 其实纵观【1】的解题过程, dijkstra和spfa本质上都是松弛边而已.

分析

题目见【1】好了. 这里先说一下思路. 直接一遍SPFA维护最短路，和次短路即可，其实和【1】是一样的~

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
80
81
82
83
84
85
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL

int n,r, head[5005], cnt, d[5005], dd[5005]; // d是最短距离数组, dd是次短距离数组
bool inq[5005];
struct Arc
{
	int from, to, nxt, len;
	Arc(){}
	Arc(int from, int to, int nxt, int len):from(from), to(to), nxt(nxt), len(len){}
}g[200005];

void addArc(int a, int b, int c)
{
	g[cnt] = Arc(a,b,head[a], c);
	head[a]= cnt++;
	g[cnt] = Arc(b,a,head[b], c);
	head[b]= cnt++;
}

int spfa()
{
	memset(inq, 0, sizeof(inq));
	queue<int> q;
	q.push(1);
	d[1] = 0;
	inq[1] = true;
	while(!q.empty())
	{
		int front = q.front();
		q.pop();
		inq[front] = false;
		for (int h = head[front],to,t,tt; ~h; h = g[h].nxt)
		{
			to = g[h].to;
			t = d[front]+g[h].len;
			tt = dd[front]+g[h].len; // 和【1】一样, 我们得到四个数 d[to]、dd[to]、t、tt, 他们从小到大排序前两名就是新的d[to]和dd[to]
			int tmp[4];
			tmp[0] = d[to], tmp[1] = dd[to], tmp[2] = t, tmp[3] = tt; // dd[to]是严格比d[to]小的(因为我们就是这样维护的)
			sort(tmp, tmp+4);
			if (d[to]>tmp[0])
			{
				d[to] = tmp[0];
				if (!inq[to])
				{
					q.push(to);
					inq[to] = true;
				}
			}
			int x = 1;
			while(x<4&&tmp[x]==tmp[0]) x++;
			if (x <4 && dd[to]> tmp[x])
			{
				dd[to] = tmp[x];
				q.push(to);
				inq[to] = true;
			}
		}
	}
	return dd[n];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n,&r);
	memset(head,-1, sizeof(head));
	memset(d, 0x3f, sizeof(d));
	memset(dd, 0x3f, sizeof(dd));
	while(r--)
	{
		int a,b,c;
		scanf("%d%d%d", &a, &b, &c);
		addArc(a,b,c);
	}
	printf("%d\n", spfa());
	return 0;
}

其实就是做spfa的时候顺便维护了一点事情. 而且让我想起了崔天翼大神的《背包九讲2.0》的9.5节讲的一段话

1
2
对于求次优解、第K优解类的问题，如果相应的最优解问题能写出状态转移方程、用动态规划解决，
那么求次优解往往可以相同的复杂度解决，第K优解则比求最优解的复杂度上多一个系数K。

注意,是相同的复杂度~

ac情况

Status Accepted
Time 250ms
Memory 3572kB
Length 1610
Lang C++
Submitted 2019-10-28 09:54:56
Shared
RemoteRunId 20997148

类似于【1】, 我们也可以使用【2】的思路进行改写. 即不要每次4个数 sort

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL

int n,r, head[5005], cnt, d[5005][2]; // d[i][0]是到i的最短距离, d[i][1]是到i的次短距离
bool inq[5005][2];

struct KK
{
	int v,c,flag;
	KK(int v, int c,int flag):v(v),c(c),flag(flag){}
};

struct Arc
{
	int from, to, nxt, len;
	Arc(){}
	Arc(int from, int to, int nxt, int len):from(from), to(to), nxt(nxt), len(len){}
}g[200005];

void addArc(int a, int b, int c)
{
	g[cnt] = Arc(a,b,head[a], c);
	head[a]= cnt++;
	g[cnt] = Arc(b,a,head[b], c);
	head[b]= cnt++;
}

int spfa()
{
	memset(d, 0x3f, sizeof(d));
	memset(inq, 0, sizeof(inq));
	queue<KK> q;
	q.push(KK(1,0,0));
	d[1][0] = 0;
	inq[1][0] = true;
	while(!q.empty())
	{
		KK front = q.front();
		q.pop();
		int v = front.v, flag = front.flag;
		inq[v][flag] = false;
		for (int h = head[v],to,t; ~h; h = g[h].nxt)
		{
			to = g[h].to, t = d[v][flag] + g[h].len;
			if (d[to][0]>t)
			{
				d[to][1] = d[to][0];
				d[to][0] = t;
				if (!inq[to][0])
				{
					inq[to][0] = true;
					q.push(KK(to, d[to][0], 0));
				}
				if (!inq[to][1])
				{
					inq[to][1] = true;
					q.push(KK(to, d[to][1], 1));
				}
			}
			else if (d[to][1]>t)
			{
				d[to][1] = t;
				if (!inq[to][1])
				{
					inq[to][1] = true;
					q.push(KK(to, d[to][1], 1));
				}
			}
		}
	}
	return d[n][1];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n,&r);
	memset(head,-1, sizeof(head));
	while(r--)
	{
		int a,b,c;
		scanf("%d%d%d", &a, &b, &c);
		addArc(a,b,c);
	}
	printf("%d\n", spfa());
	return 0;
}

ac情况

Status Accepted
Time 235ms
Memory 3756kB
Length 1624
Lang C++
Submitted 2019-10-28 20:46:20
Shared
RemoteRunId 20998989

参考

【1】https://yfsyfs.github.io/2019/08/21/poj-3255-Roadblocks-dijkstra/

【2】https://yfsyfs.github.io/2019/10/28/poj-3463-Sightseeing-%E6%9C%80%E7%9F%AD%E8%B7%AF%E6%AC%A1%E7%9F%AD%E8%B7%AF%E7%9A%84%E6%9D%A1%E6%95%B0-dijkstra/