题目链接：点我啊╭(╯^╰)╮
题目大意：
有 m m m 个休息站，起点为 d 1 d_1 d1?，终点为 d m d_m dm?
绿灯时间为 g g g，绿灯时间内必须一直走
红灯时间为 r r r，禁止走，且红灯时间内必须在休息站
只有在休息站内可以调整方向，红绿灯交替
求最短时间
解题思路：
d p [ i ] [ j ] dp[i][j] dp[i][j] 为到达 i i i 这个休息站，绿灯时间为 j j j，经历了最少的红灯次数
这样转移的边权只能是 + 1 （ j = = g ） +1（j==g） +1（j==g），或者 + 0 （ j < g ） +0（j<g） +0（j<g）
就可以用 d e q u e deque deque 维护 01 b f s 01bfs 01bfs 来解决
边权为 1 1 1 的放在队尾，边权为 0 0 0 的放在队首
注意不能在结束的时候再计算答案，可能会多计算一次红灯
#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 1e4 + 5;
const int maxm = 1e3 + 5;
int n, d[maxn], g, r;
int dp[maxn][maxm];
bool vis[maxn][maxm];
struct node {int p, g, r;
};
deque <node> q;void go(node u, int v) {if(v < 1 || v > n) return;int dis = abs(d[u.p] - d[v]);if(u.g + dis > g) return;assert(u.r == dp[u.p][u.g]);if(u.g + dis == g) {if(!vis[v][0]) {dp[v][0] = u.r + 1; vis[v][0] = 1;q.push_back({v, 0, u.r + 1});}} else {int ng = u.g + dis;if(!vis[v][ng]) {dp[v][ng] = u.r; vis[v][ng] = 1;q.push_front({v, ng, u.r});}}
}signed main() {scanf("%d%d", &n, &n);for(int i=1; i<=n; i++) scanf("%d", d+i);scanf("%d%d", &g, &r); sort(d+1, d+1+n);dp[1][0] = 0; vis[1][0] = 1;q.push_front({1, 0, 0});ll ans = 1e18;while(q.size()) {node u = q.front(); q.pop_front();if(u.g == 0 && d[n] - d[u.p] <= g) ans = min(ans, 1ll * dp[u.p][u.g] * (g + r) + d[n] - d[u.p]);go(u, u.p - 1), go(u, u.p + 1);}printf("%lld\n", ans == 1e18 ? -1ll : ans);
}