https://codeforces.com/contest/1341
E. Nastya and Unexpected Guest
题意：从坐标0出发，要到坐标n，中间有一些安全岛，绿灯持续g秒，红灯持续r秒，红灯时必须在安全岛上等待，且在安全岛上可以改变方向。每秒移动1，要求最少时间到达坐标n。
状态 (u, t) 表示（坐标，绿灯剩余时间），每次转移到相邻安全岛，然后 bfs，初始 (0, g)，目标是 (n, 任意)。
spfa可以过，但是卡时间。绝对不是正解。
01bfs
第一次听说这东西。
spfa的复杂度为 O((E+V)log(E+V))，之所以会多出来个log，就是因为用堆维护了距离从小到大。
但是对于边权只有0或1的图来说，可以通过一个deque，把经过边权1得到的状态放到队尾，经过边权0得到的状态放到队首，这样自然得到有序的队伍，而少了log。
还要转化问题为01的图。
状态（u，t）仍然表示（坐标，绿灯剩余时间），但是距离不再是时间，而是经过的红绿灯轮数，则每次状态转移最多经过一次红灯，也就是轮数最多增加一轮。则若转移到的状态绿灯剩余时间为0，经过边权1，否则边权0。
注意到终点，剩余时间g这种特殊情况。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
int n, m;
int a[N], g, r;
int d[10010][1010];
typedef pair<int, int>pii;
int vis[10010][1010];
int bfs() {
int ans = INF;
deque<pii>q;
q.push_back(pii(1, g));
vis[1][g] = 1;
while (!q.empty()) {
pii tp = q.front(); q.pop_front();
int x = tp.first, t = tp.second;
if (x == m) {
if (t == g) {
ans = min(ans, (r + g)*d[x][t] - r);
}
else
ans = min(ans, n - a[x] + g - t + (g + r)*d[x][t]);
}
if (x > 1 && a[x] - a[x - 1] <= t) {
int nt = t - (a[x] - a[x - 1]);
if (nt == 0)nt = g;
if (!vis[x - 1][nt]) {
vis[x - 1][nt] = 1;
if (nt == g) {
d[x - 1][nt] = d[x][t] + 1;
q.push_back(pii(x - 1, nt));
}
else {
d[x - 1][nt] = d[x][t];
q.push_front(pii(x - 1, nt));
}
}
}
if (x < m && a[x + 1] - a[x] <= t) {
int nt = t - (a[x + 1] - a[x]);
if (nt == 0)nt = g;
if (vis[x + 1][nt])continue;
vis[x + 1][nt] = 1;
if (nt == g) {
d[x + 1][nt] = d[x][t] + 1;
q.push_back(pii(x + 1, nt));
}
else {
d[x + 1][nt] = d[x][t];
q.push_front(pii(x + 1, nt));
}
}
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d", &a[i]);
}
sort(a + 1, a + m + 1);
scanf("%d%d", &g, &r);
int ans = bfs();
printf("%d\n", ans == INF ? -1 : ans);
return 0;
}
|
