sdutoj 3468 广度优先搜索练习之神奇的电梯

缘起

继续死磕电梯 sdutoj 3468 广度优先搜索练习之神奇的电梯

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
Problem Description
有一座已知层数为n的高楼，这座高楼的特殊之处在于只能靠电梯去上下楼，所以要去到某一层要非常耽误时间，然而
更悲哀的是，这座高楼的电梯是限号的，小鑫最开始的时候在1层，他想去第x层，问题是他最起码要经过多少层
(包含第x层)才能到达第x层。

Input
多组输入。
第一行是三个正整数n,m,q。分别代表楼的总层数，给定的m条信息和q次查询。
接下来的m行，每行的第一个整数pos代表这是第pos层的电梯，第二个数代表从这一层可以去的楼层总共有num个，之后的num个数字代表从第pos层代表可以去的楼层。
最后的q行，每行一个整数代表小鑫想去的楼层号码。
1<=m,pos,num<=n<=200
1<=q<=20

Output
对于每次询问输出一个整数，占一行。代表如果要去某个楼层最少要经过多少层，如果到不了的话就输出-1。

Sample Input
10 4 3
1 2 6 7
3 4 4 6 8 10
5 2 2 3
7 3 10 5 6
4
5
9

Sample Output
5
3
-1

限制
1s

唉，题目已经非常仁慈了~ 直接告诉你算法了. 如果你再不按照它的来，是不是太对不起出题人了? 嘿嘿~

每部电梯其实就是一张有向带权图, 所以并不能使用朴素的bfs. 因为朴素的bfs的代价函数并不和权值相符（详细理论参见 【1】）. 本题可以使用启发式函数恒为0（毕竟n并不大），则就可以使用优先队列式分支限界法. 其中真实代价函数为迄今为止走的楼层数. 而启发式函数为0. 不需要剪枝——因为启发式函数<=真实走完剩余路的代价函数. 而且因为重新发现节点并不能降低g的值. 所以死去的节点不需要复活. 所以开一个数组isvisited进行哈希即可.

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
//#define LOCAL
#define ABS(a,b) ((a)>(b)?((a)-(b)):((b)-(a)))
const int maxn=  205;
int n,m,q, head[maxn],cnt;
struct Arc
{
	int from,to, len, nxt;
}g[40005];

bool v[maxn];

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

struct Node
{
	int level, g; // level是当前的楼层, g是迄今为止的真实代价函数
	Node(int level, int g):level(level),g(g){}
	bool operator<(const Node &o) const
	{
		return g>o.g; // g越大,优先级越小
	}
};

int bb(int target) // 分支限界要去target
{
	memset(v, 0, sizeof(v));
	priority_queue<Node> pq; // 小根堆
	pq.push(Node(1,0));
	v[1] = true;
	while(!pq.empty())
	{
		Node top = pq.top();
		pq.pop();
		if (top.level==target)
		{
			return top.g;
		}
		for (int h = head[top.level],to; ~h; h = g[h].nxt)
		{
			to = g[h].to;
			if (v[to])
			{
				continue;;
			}
			v[to] = true;
			pq.push(Node(to, top.g+ABS(top.level, to)));
		}
	}
	return -1;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d%d%d", &n,&m, &q))
	{
		memset(head, -1, sizeof(head));
		cnt = 0;
		while(m--)
		{
			int pos,num;
			scanf("%d%d", &pos, &num);
			while(num--)
			{
				int k;
				scanf("%d", &k);
				addArc(pos, k, ABS(pos,k));
			}
		}
		while(q--)
		{
			int qq;
			scanf("%d", &qq);
			printf("%d\n", bb(qq));
		}
	}
	return 0;
}

但是WA了. 因为我上面的程序得到的测试数据的答案都是

1
2
3
11
8
-1

而不是

1
2
3
5
3
-1

其实原题想问的是”最少转乘几次”，而不是最少经过多少楼层.但是傻逼的题目没说清楚. 两种问法将导致完全不同的解法的. 如果是”最少转乘几次”, 那必然是bfs 因为目标函数和bfs的代价函数是一致的. 如果是”最少经过多少楼层”, 则就是分支限界. 所以用bfs来打

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
//#define LOCAL
#define ABS(a,b) ((a)>(b)?((a)-(b)):((b)-(a)))
const int maxn=  205;
int n,m,q, head[maxn],cnt;
struct Arc
{
	int from,to, len, nxt;
}g[40005];

bool v[maxn];

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

struct Node
{
	int level, step; // 当前节点的楼层, 以及经过了几步
	Node(int level, int step):level(level), step(step){}
};

int bfs(int target) // 宽搜target
{
	memset(v, 0, sizeof(v));
	queue<Node> q;
	v[1] = true;
	q.push(Node(1,1));
	while(!q.empty())
	{
		Node front = q.front();
		q.pop();
		if (front.level==target)
		{
			return front.step;
		}
		for (int h = head[front.level],to; ~h; h = g[h].nxt)
		{
			to = g[h].to;
			if (v[to])
			{
				continue;;
			}
			v[to] = true;
			q.push(Node(to, front.step+1));
		}
	}
	return -1;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d%d%d", &n,&m, &q))
	{
		memset(head, -1, sizeof(head));
		cnt = 0;
		while(m--)
		{
			int pos,num;
			scanf("%d%d", &pos, &num);
			while(num--)
			{
				int k;
				scanf("%d", &k);
				addArc(pos, k, ABS(pos,k));
			}
		}
		while(q--)
		{
			int qq;
			scanf("%d", &qq);
			printf("%d\n", bfs(qq));
		}
	}
	return 0;
}

ac情况

6528122 yfs 3468 Accepted 20 ms 216 KiB g++ 1510 B 2019-09-11 11:05:09

参考

【1】https://yfsyfs.github.io/2019/09/05/%E5%88%86%E6%94%AF%E9%99%90%E7%95%8C-bfs-%E6%90%9C%E7%B4%A2-%E7%9A%84%E4%B8%80%E8%88%AC%E6%80%A7%E8%AE%BA%E8%BF%B0/