CF1341E. Nastya and Unexpected Guest（01bfs）

Unexpected Guest（01bfs）"/>

CF1341E. Nastya and Unexpected Guest（01bfs）

If the girl doesn’t go to Denis, then Denis will go to the girl. Using this rule, the young man left home, bought flowers and went to Nastya.

On the way from Denis’s house to the girl’s house is a road of 𝑛 lines. This road can’t be always crossed in one green light. Foreseeing this, the good mayor decided to place safety islands in some parts of the road. Each safety island is located after a line, as well as at the beginning and at the end of the road. Pedestrians can relax on them, gain strength and wait for a green light.

Denis came to the edge of the road exactly at the moment when the green light turned on. The boy knows that the traffic light first lights up 𝑔 seconds green, and then 𝑟 seconds red, then again 𝑔 seconds green and so on.

Formally, the road can be represented as a segment [0,𝑛]. Initially, Denis is at point 0. His task is to get to point 𝑛 in the shortest possible time.

He knows many different integers 𝑑1,𝑑2,…,𝑑𝑚, where 0≤𝑑𝑖≤𝑛 — are the coordinates of points, in which the safety islands are located. Only at one of these points, the boy can be at a time when the red light is on.

Unfortunately, Denis isn’t always able to control himself because of the excitement, so some restrictions are imposed:

He must always move while the green light is on because it’s difficult to stand when so beautiful girl is waiting for you. Denis can change his position by ±1 in 1 second. While doing so, he must always stay inside the segment [0,𝑛].
He can change his direction only on the safety islands (because it is safe). This means that if in the previous second the boy changed his position by +1 and he walked on a safety island, then he can change his position by ±1. Otherwise, he can change his position only by +1. Similarly, if in the previous second he changed his position by −1, on a safety island he can change position by ±1, and at any other point by −1.
At the moment when the red light is on, the boy must be on one of the safety islands. He can continue moving in any direction when the green light is on.
Denis has crossed the road as soon as his coordinate becomes equal to 𝑛.

This task was not so simple, because it’s possible that it is impossible to cross the road. Since Denis has all thoughts about his love, he couldn’t solve this problem and asked us to help him. Find the minimal possible time for which he can cross the road according to these rules, or find that it is impossible to do.

Input
The first line contains two integers 𝑛 and 𝑚 (1≤𝑛≤106,2≤𝑚≤𝑚𝑖𝑛(𝑛+1,104)) — road width and the number of safety islands.

The second line contains 𝑚 distinct integers 𝑑1,𝑑2,…,𝑑𝑚 (0≤𝑑𝑖≤𝑛) — the points where the safety islands are located. It is guaranteed that there are 0 and 𝑛 among them.

The third line contains two integers 𝑔,𝑟 (1≤𝑔,𝑟≤1000) — the time that the green light stays on and the time that the red light stays on.

Output
Output a single integer — the minimum time for which Denis can cross the road with obeying all the rules.

If it is impossible to cross the road output −1.

Examples
inputCopy
15 5
0 3 7 14 15
11 11
outputCopy
45
inputCopy
13 4
0 3 7 13
9 9
outputCopy
-1
Note
In the first test, the optimal route is:

for the first green light, go to 7 and return to 3. In this case, we will change the direction of movement at the point 7, which is allowed, since there is a safety island at this point. In the end, we will be at the point of 3, where there is also a safety island. The next 11 seconds we have to wait for the red light.
for the second green light reaches 14. Wait for the red light again.
for 1 second go to 15. As a result, Denis is at the end of the road.
In total, 45 seconds are obtained.

In the second test, it is impossible to cross the road according to all the rules.

题意：
一条路长度为 n n n，从0出发。有 m m m个站点。
绿灯红灯交替变换。绿灯的时候你必须走，且从一个站点出来后方向是确定的。
红灯的时候必须在一个站点上。求最短多少时间可以到达 n n n点。

思路：
可以算作广义的最短路。
定义 d [ i ] [ j ] d[i][j] d[i][j]为到了第 i i i个站点时，绿灯当前时间为 j j j，经过了多少轮红绿灯变换。
如果你定义 d [ i ] [ j ] d[i][j] d[i][j]为到了这个状态的最短时间，那么很明显就是求一个最短路了。

但是官方题解的定义好处在于，转移中唯一有权值的边为 d [ i ] [ g ] − > d [ i ] [ 0 ] d[i][g]->d[i][0] d[i][g]−>d[i][0],这意味着等一个红灯。这就变成了01bfs问题。意思就是权值只有0和1。这种问题的解法是边权为1的节点入队尾。边权为0的节点入队首。

所能转移到的子节点就是 d [ i − 1 ] [ k ] d[i-1][k] d[i−1][k], d [ i + 1 ] [ k ] d[i+1][k] d[i+1][k], d [ i ] [ 0 ] d[i][0] d[i][0]。

#include <cstdio>
#include <algorithm>
#include <map>
#include <iostream>
#include <vector>
#include <deque>using namespace std;
typedef long long ll;int n,m;
int g,r;
int d[10007][1007];
bool vis[10007][1007];
int a[10007];struct Node {int p,v;
};ll bfs() {deque<Node>q;q.push_back({0,0});vis[0][0] = 1;ll ans = -1;while(!q.empty()) {Node now = q.front();q.pop_front();if(now.v == 0) { //可以证明当一个点可以直接走到终点的时候，其肯定是一个绿灯时间为0的点走过来的，所以我们只判断now.v==0的情况int rem = n - a[now.p]; //你也可以对所有点进行判断。if(rem <= g) {ll tmp = 1ll * d[now.p][now.v] * (g + r) + rem;if(ans == -1 || tmp < ans) {ans = tmp;}}}if(now.v == g) {if(!vis[now.p][0]) {d[now.p][0] = d[now.p][now.v] + 1;vis[now.p][0] = 1;q.push_back({now.p,0});}continue;}if(now.p > 1) {int p = now.p - 1;int v = now.v + a[now.p] - a[p];if(v <= g && !vis[p][v]) {vis[p][v] = 1;d[p][v] = d[now.p][now.v];q.push_front({p,v});}}if(now.p < m) {int p = now.p + 1;int v = now.v + a[p] - a[now.p];if(v <= g && !vis[p][v]) {vis[p][v] = 1;d[p][v] = d[now.p][now.v];q.push_front({p,v});}}}return ans;
}int main() {scanf("%d%d",&n,&m);for(int i = 1;i <= m;i++) {scanf("%d",&a[i]);}scanf("%d%d",&g,&r);sort(a + 1,a + 1 + m);printf("%lld\n",bfs());return 0;
}