poj 3463 Sightseeing 最短路次短路的条数 dijkstra

缘起

【1】和【2】中我们通过dijkstra、spfa两种方法给出了次短路模板. 现在我们研究次短路的条数问题. poj 3463 Sightseeing

分析

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
旅行团每天固定的从S地出发到达F地，为了省油要求尽量走最短路径或恰好比最短路径长1单位距离的路径
求满足条件的路径条数

【输入】
多样例.第一行是样例数. 然后每个样例开始于n和m,
2 ≤ N ≤ 1,000 and 1 ≤ M ≤ 10, 000
n是城市的个数, m是有向弧（即单向的）的条数. 然后是m行, 每行三个正整数A,B,L, 
1 ≤ A, B ≤ N, A ≠ B and 1 ≤ L ≤ 1,000,
表示从A到B的弧长L
最后一行是两个整数S和F, 1 ≤ S, F ≤ N and S != F, 即为题目中的起点和终点.

【输出】
对每个样例, 输出最短路或者恰好比它长1的次短路的条数之和. 输入保证答案最多1e9条。

【样例输入】
2
5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
5 2 7
4 1

【样例输出】
3
2

【限制】
2s

其实和【1】、【2】一样,也都是在跑dijkstra或者spfa的时候顺便维护一些事情而已. 但是本文结合了【3】的优化（更快的板子）以及使用了比【1】、【2】更好理解的方式（之所以说是更加好的理解方式是因为它每次从堆中弹出的状态区分了到底是最短路还是次短路（通过flag），其实flag的作用根本不在于鉴别最短路还是次短路(代码里面根本没有用flag进行判断的),而是在于44行防止重复计数num.也就是说, 如果不是本题要计数num的话, 根本没必要使用flag）， 即下面的 if…else if…else if… 仅仅针对当前出堆的状态来更新. 以后做次短路就用这种方式, 学到了~

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL
const int maxn = 1005, maxm = 10005;
int n,m, d[maxn][2], num[maxn][2], head[maxn],cnt,s,f; // d[i][0](d[i][1])是到达i顶点的最（次）短路, num[i][0]（num[i][1]）是到达i顶点的最（次）短路的条数
struct KK
{
	int v, c, flag; // v表示顶点, c表示路径长度, flag=0表示最短路,flag=1表示次短路
	KK(int v,int c,int flag):v(v),c(c),flag(flag){}
	bool operator <(const KK &o) const
	{
		return c>o.c; // c越大, 优先级越低
	}
};
bool v[maxn][2];
struct Arc
{
	int from,to,nxt,len;
}g[maxm];

void addarc(int from, int to, int len)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].len = len, g[cnt].nxt = head[from];
	head[from] = cnt++;
}

int solve()
{
	memset(d, 0x3f, sizeof(d));
	memset(num,0,sizeof(num));
	memset(v, 0, sizeof(v));
	d[s][0] = 0;
	num[s][0] = 1;
	priority_queue<KK > pq;
	pq.push(KK(s,0,0));
	while(!pq.empty())
	{
		KK top = pq.top();
		pq.pop();
		int h = top.v, flag = top.flag;
		if (v[h][flag]) // 如果状态达到过, 则不必再扩展了, 这就是【3】中最后提及的优化"更快的板子"
		{
			continue;
		}
		v[h][flag] = true;
		for (int i = head[h],to, t; ~i; i = g[i].nxt) // 下面的if...else if...else if 更加容易理解~
		{
			to  = g[i].to;
			t = d[h][flag]+g[i].len; // 松弛的长度
			if (!v[to][0] && d[to][0] > t) // 更新最短路、次短路
			{
				d[to][1] = d[to][0];
				num[to][1] = num[to][0]; // 更新次短路
				d[to][0] = t;
				num[to][0] = num[h][flag]; // 更新最短路
				pq.push(KK(to, d[to][1], 1));
				pq.push(KK(to, d[to][0], 0));
			}
			else if (!v[to][0] && d[to][0] == t) // 更新最短路方法数
			{
				num[to][0] += num[h][flag]; // 为什么可以直接相加, 是因为(h,flag) 是首次出现(上面的continue起的作用), 所以一定和原先的num[to][0]中的方案不重复
			}
			else if (!v[to][1] && d[to][1]>t) // 更新最短路
			{
				d[to][1] = t;
				num[to][1] = num[h][flag];
				pq.push(KK(to, d[to][1], 1));
			}
			else if (!v[to][1] && d[to][1] == t) // 更新次短路的方法数
			{
				num[to][1] += num[h][flag]; // 能直接相加的原因和上面更新最短路方法数的理由相同
			}
		}
	}
	if (d[f][0]+1==d[f][1]) // 如果次短路的确仅仅比最短路长1的话
	{
		num[f][0] += num[f][1];
	}
	return num[f][0];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		cnt = 0;
		memset(head, -1, sizeof(head));
		scanf("%d%d", &n,&m);
		while(m--)
		{
			int a,b,l;
			scanf("%d%d%d", &a, &b, &l);
			addarc(a,b,l);
		}
		scanf("%d%d", &s, &f);
		printf("%d\n", solve());
	}
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 408kB
Length 2357
Lang C++
Submitted 2019-10-28 16:44:55
Shared
RemoteRunId 20997897

其实, 在松弛的时候不加 !v[][] 这样的判断也是可以的.

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL
const int maxn = 1005, maxm = 10005;
int n,m, d[maxn][2], num[maxn][2], head[maxn],cnt,s,f; 
struct KK
{
	int v, c, flag; 
	KK(int v,int c,int flag):v(v),c(c),flag(flag){}
	bool operator <(const KK &o) const
	{
		return c>o.c; 
	}
};
bool v[maxn][2];
struct Arc
{
	int from,to,nxt,len;
}g[maxm];

void addarc(int from, int to, int len)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].len = len, g[cnt].nxt = head[from];
	head[from] = cnt++;
}

int solve()
{
	memset(d, 0x3f, sizeof(d));
	memset(num,0,sizeof(num));
	memset(v, 0, sizeof(v));
	d[s][0] = 0;
	num[s][0] = 1;
	priority_queue<KK > pq;
	pq.push(KK(s,0,0));
	while(!pq.empty())
	{
		KK top = pq.top();
		pq.pop();
		int h = top.v, flag = top.flag;
		if (v[h][flag]) 
		{
			continue;
		}
		v[h][flag] = true;
		for (int i = head[h],to, t; ~i; i = g[i].nxt) 
		{
			to  = g[i].to;
			t = d[h][flag]+g[i].len; 
			if (d[to][0] > t) // 在松弛的时候不加 !v[][] 这样的判断也是可以的
			{
				d[to][1] = d[to][0];
				num[to][1] = num[to][0]; 
				d[to][0] = t;
				num[to][0] = num[h][flag]; 
				pq.push(KK(to, d[to][1], 1));
				pq.push(KK(to, d[to][0], 0));
			}
			else if (d[to][0] == t) 
			{
				num[to][0] += num[h][flag]; 
			}
			else if (d[to][1]>t) 
			{
				d[to][1] = t;
				num[to][1] = num[h][flag];
				pq.push(KK(to, d[to][1], 1));
			}
			else if (d[to][1] == t) 
			{
				num[to][1] += num[h][flag]; 
			}
		}
	}
	if (d[f][0]+1==d[f][1]) 
	{
		num[f][0] += num[f][1];
	}
	return num[f][0];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		cnt = 0;
		memset(head, -1, sizeof(head));
		scanf("%d%d", &n,&m);
		while(m--)
		{
			int a,b,l;
			scanf("%d%d%d", &a, &b, &l);
			addarc(a,b,l);
		}
		scanf("%d%d", &s, &f);
		printf("%d\n", solve());
	}
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 412kB
Length 2305
Lang C++
Submitted 2019-10-29 07:28:21
Shared
RemoteRunId 21000037

参考

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

【2】https://yfsyfs.github.io/2019/10/28/POJ-3255-Roadblocks-%E6%AC%A1%E7%9F%AD%E8%B7%AF%E6%A8%A1%E6%9D%BF-spfa/

【3】https://yfsyfs.github.io/2019/08/22/hdu-2544-dijkstra%E6%A8%A1%E6%9D%BF/