牛客多校3 - Journey（建图，最短路）

https://ac.nowcoder.com/acm/contest/33188/J

题意
给定一个 n 个点的图，每个点都是一个十字路口，和相邻的四个十字路口之间连边。

从一条路径经过十字路口直走，左转或者掉头，花费 1 ；右转不花费。

对于每个十字路口 $i$ 给出 $c_{i,1},c_{i,2},c_{i,3},c_{i,4}$，逆时针依次为相邻的四个十字路口编号。

现在给出出发路径 $<s1,s2>$，求到达​终点路径 $<t1,t2>$ 的最小花费。

注意路径方向，$<a,b>$ 和 $<b,a>$ 不同。

$2\le n\le 500000$

思路
把每一条路径看作一个点，然后两条路径之间连边，新边权根据两条路径的位置赋值，重新建图。
每个十字路口最多产生 8 个新点，所以最终点数不超过 8*n，最多产生 12 条新边，所以最终点数不超过 12*n。

对于把两个点哈希成一个点，有两种方法：

1. 将 (x, y) 哈希成 x*n + y，然后用 unordered_map 映射这个大数。
2. 直接用 map 映射 pair，但是 map 每次查询的复杂度高，而unordered_map不能直接映射pair。但是可以重写 unordered_map 的比较方式后映射 pair。

struct cmp{
	int operator()(PII A)const{
		return A.fi * 521427 + A.se;
	}
};
unordered_map<PII, int, cmp> mp;
1
2
3
4
5
6

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'

const int N = 4000010, mod = 1e9+7;
int T, n, m;
int a[4];
vector<PII> e[N];
int st, en;
int f[N], dist[N];
int idx;

struct cmp{
	int operator()(PII A)const{
		return A.fi * 521427 + A.se;
	}
};

unordered_map<PII, int, cmp> mp;

int get(int x, int y){
	if(mp.count({x, y})) return mp[{x, y}];
	mp[{x, y}] = ++idx;
	return idx;
}

void dij()
{
	for(int i=1;i<=idx;i++) dist[i] = 1e9;
	dist[st] = 0;
	
	deque<int> que;
	que.push_front(st);
	
	while(que.size())
	{
		int x = que.front(); que.pop_front();
		if(f[x]) continue;
		f[x] = 1;
		
		for(auto it : e[x])
		{
			int tx = it.fi, dis = it.se;
			if(dist[tx] > dist[x] + dis)
			{
				dist[tx] = dist[x] + dis;
				if(dis) que.push_back(tx);
				else que.push_front(tx);
			}
		}
	}
}

signed main(){
	scanf("%lld", &n);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<4;j++) scanf("%lld", &a[j]);
		for(int j=0;j<4;j++)
		{
			if(a[j] && a[(j+1)%4]){
				int x = get(a[j], i), y = get(i, a[(j+1)%4]);
				e[x].push_back({y, 0});
				x = get(a[(j+1)%4], i), y = get(i, a[j]);
				e[x].push_back({y, 1});
			}
			
			if(a[j])
			{
				int x = get(a[j], i), y = get(i, a[j]);
				e[x].push_back({y, 1});
//				e[y].push_back({x, 1});
			}
		}
		for(int j=0;j<2;j++)
		{
			if(a[j] == 0 || a[(j+2)%4] == 0) continue;
			int x = get(a[j], i), y = get(i, a[(j+2)%4]);
			e[x].push_back({y, 1});
			x = get(a[(j+2)%4], i), y = get(i, a[j]);
			e[x].push_back({y, 1});
		}
	}
	
	int a, b, c, d;
	scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
	st = get(a, b), en = get(c, d);
	
	dij();
	
	if(dist[en] != 1e9) cout << dist[en];
	else cout << -1;
	
	return 0;
}
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

经验
要敢想，敢建图！