#include<cstdio>
#include<algorithm>
#include<map>
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
typedef long long ll;
const int N=10010,M=1010;
int n,m;
int g,r;
//定义d[i,j]为到了第i个站点时,绿灯当前时间为j,经过了多少轮红绿灯变换。
int d[N][M];
bool vis[N][M];
int a[N];
struct node
{
//p表示在那个安全岛
int p;
//绿灯经过了多久
int 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)//刚等完红灯
{
//因为刚等完红灯，所以此时肯定在安全岛
//在第几个安全岛，还剩下几个点
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])
{
//次数+1
d[now.p][0]=d[now.p][now.v]+1;
//访问过了
vis[now.p][0]=1;
//加入丢列
q.push_back({now.p,0});
}
continue;
}
//如果安全岛的序号大于1
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});
}
}
//如果安全岛的序号小于m
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()
{
cin>>n>>m;
//安全岛的位置
for(int i=1; i<=m; i++)
cin>>a[i];
cin>>g>>r;
sort(a+1,a+1+m);
cout<<bfs()<<endl;
return 0;
}
Codeforces Round #637 (Div. 2) - Thanks, Ivan Belonogov! E—Nastya and Unexpected Guest (01bfs)
原文：https://www.cnblogs.com/QingyuYYYYY/p/12790710.html