poj 2686 Traveling by Stagecoach dijkstra DAG DP 状态压缩

缘起

日常浪费生命~ poj 2686 Traveling by Stagecoach

分析

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
一个旅行家计划乘坐马车周游旅行. 他所在的国家有m个城市. 在城市之间有若干道路. 从某个城市
沿着某条道路到相邻的城市需要乘坐马车. 而乘坐马车需要车票. 每用一张车票只可以通过一条道路.
每张车票上印有马匹的数量. 从一个城市移动到另一个城市需要的时间等于城市之间的道路的长度除以
马匹的数量. 这位旅行家有n张车票. 第i张车票上印有的马匹数量是ti. 一张车票只能用一次. 
求该旅行家从a城市到b城市需要的最短时间. 如果无法抵达b城市的话, 输出 "Impossible"
1<=n<=8, 2<=m<=30, 1<=a,b<=m(a!=b), 1<=ti<=10, 1<=道路的长度<=100

【输入】
多样例. 每个样例形如
n m p a b
t1 t2 ... tn
x1 y1 z1
x2 y2 z2
...
xp yp zp
都是非负整数. 最后一个样例是5个0, 不需要处理. p是道路数量(可能是0)
输入保证两座城市之间有多条道路. 也没有一条道路通往自己. 道路都是双向的.

【输出】
最短时间（精确到小数点第三位）或者 "Impossible"

【样例输入】
3 4 3 1 4
3 1 2
1 2 10
2 3 30
3 4 20
2 4 4 2 1
3 1
2 3 3
1 3 3
4 1 2
4 2 5
2 4 3 4 1
5 5
1 2 10
2 3 10
3 4 10
1 2 0 1 2
1
8 5 10 1 5
2 7 1 8 4 5 6 3
1 2 5
2 3 4
3 4 7
4 5 3
1 3 25
2 4 23
3 5 22
1 4 45
2 5 51
1 5 99
0 0 0 0 0

【样例输出】
30.000
3.667
Impossible
Impossible
2.856

【限制】
2s

将到达城市u, 剩余车票集合为S视作一种状态（或者有向图上的顶点）. 则该旅行家的旅行其实可以视作是这种状态之间的转移.

而车票仅仅有8张, 所以可以使用二进制压缩车票的状态. 一共 2^8=256种状态——即旅行家在一个城市u, 其实有256种状态. 而城市不超过30座. 所以该有向图（其实是DAG）的顶点个数<=256*30

注意哈，这是有向图，因为从一个顶点（状态）到另一个状态是不可逆的.

所以算法是

读入一条边，例如u城市和v城市之间的道路长L. 则建立 (u,S)到(v,T)的弧. 其中T是S的子集，而且T比S恰好少了一个元素（即用掉的车票）.则弧的长度就是L除以车票的ti值.

同样，我们也要建立v到u的弧. 然后统计出度为0的点（即状态）. 这些点就是拓扑排序的起点. 然后进行拓扑排序. 拓扑排序每出来一个点就可以得到到达该点（状态）的最短时间了.

注意，虽然是求单源最短路，但是由于是DAG，所以不需要使用dijkstra. 只需要拓扑排序+DP即可

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
109
110
111
112
113
114
115
116
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <stack>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,m,p,a,b,t[10],head[9005],cnt,indeg[9005],full;
double dis[9005];

struct Arc
{
	int from, to, nxt;
	double len; // len是两个状态之间转移的时间
}g[4000005]; // 4w是yy出来的

void addArc(int from, int to, double len) // 加弧 from->to 长度为len
{
	indeg[to]++;
	g[cnt].from = from, g[cnt].to = to, g[cnt].len = len, g[cnt].nxt = head[from];
	head[from] = cnt++;
}

void add(int x, int y, int z)
{
	int xx = (x-1)*full, yy = (y-1)*full;
	for (int i = full-1; ~i; i--)
	{
		for (int j = 0; j<n; j++)
		{
			if (i&(1<<j)) // 如果有第j张车票(0<=j<n)
			{
				addArc(xx+i, yy+(i&~(1<<j)), 1.0*z/t[j]); // i去掉第j张车票
			}
		}
	}
}

void build(int x, int y, int z) // x和y之间有长度为z的边
{
	add(x,y,z); 
	add(y,x,z); // 双向都要加弧
}

void topsort()
{
	stack<int> s;
	for (int i = 0; i<full*m; i++) // 有向图的顶点从0到full*m-1, 每full个顶点构成了一个原无向图顶点的各种车票状态
	{
		if (!indeg[i])
		{
			s.push(i);
		}
	} // 初始化拓扑排序用的栈
	while(!s.empty())
	{
		int top = s.top();
		s.pop();
		for (int h = head[top],to; ~h; h = g[h].nxt)
		{
			to = g[h].to;
			dis[to] = min(dis[to], dis[top] + g[h].len); // 松弛, 在拓扑排序的过程中进行dp
			if (!--indeg[to])
			{
				s.push(to);
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(scanf("%d%d%d%d%d", &n,&m,&p,&a,&b), n||m||p||a||b)
	{
		full = (1<<n);
		memset(head, -1, sizeof(head));
		memset(indeg, 0, sizeof(indeg));
		cnt = 0;
		for (int i = 0;i<full*m; i++)
		{
			dis[i] = 0x3f3f3f3f; // 初始化到单源(a*full-1)的最短距离
		}
		for (int i = 0;i<n;i++)
		{
			scanf("%d", t+i);
		}
		while(p)
		{
			int x,y,z;
			scanf("%d%d%d", &x,&y,&z); // x和y之间的边长度为z
			build(x,y,z);
			p--;
		}
		dis[a*full-1] = 0; // 单源
		topsort();
		double ans = 0x3f3f3f3f;
		for (int i = full*(b-1); i<full*b; i++)
		{
			ans = min(ans, dis[i]);
		}
		if (ans>=0x3f3f3f3f)
		{
			puts("Impossible");
		}
		else
		{
			printf("%.3lf\n", ans);
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 1344ms
Memory 21212kB
Length 1978
Lang C++
Submitted 2019-09-18 21:29:25
Shared
RemoteRunId 20872993