算法1
(分层图最短路)
C++ 代码
#include <bits/stdc++.h>
#define For(i, a, b) for(register int i = (a); i <= (b); ++i)
#define Rof(i, a, b) for(register int i = (a); i >= (b); --i)
#define INF 0x3f3f3f3f
#define LL long long
#define MaxN 2010
using namespace std;
int N, M, Dis[MaxN][21], A[21], SC;
bool Inq[MaxN][21];
struct Xjh {int Dot, WZ;};
queue<Xjh> Q;
bool Check(int x) {return x >= 1 && x <= N;}
int main() {
scanf("%d%d", &N, &M); For(i, 1, M) scanf("%d", &A[i]), SC = A[i] ? SC : i;
memset(Dis, INF, sizeof(Dis)); Dis[1][SC] = 0; Inq[1][SC] = 1; Q.push((Xjh){1, SC});
while(!Q.empty()) {
Xjh Now = Q.front(); Q.pop(); Inq[Now.Dot][Now.WZ] = 0;
if(Check(Now.Dot + A[Now.WZ])) {
int v = Now.Dot + A[Now.WZ];
if(Dis[v][Now.WZ] > Dis[Now.Dot][Now.WZ] + 2 * abs(A[Now.WZ])) {
Dis[v][Now.WZ] = Dis[Now.Dot][Now.WZ] + 2 * abs(A[Now.WZ]);
if(!Inq[v][Now.WZ]) Inq[v][Now.WZ] = 1, Q.push((Xjh){v, Now.WZ});
}
}
if(Now.WZ > 1) {
int nw = Now.WZ - 1;
if(Dis[Now.Dot][nw] > Dis[Now.Dot][Now.WZ] + 1) {
Dis[Now.Dot][nw] = Dis[Now.Dot][Now.WZ] + 1;
if(!Inq[Now.Dot][nw]) Inq[Now.Dot][nw] = 1, Q.push((Xjh){Now.Dot, nw});
}
}
if(Now.WZ < M) {
int nw = Now.WZ + 1;
if(Dis[Now.Dot][nw] > Dis[Now.Dot][Now.WZ] + 1) {
Dis[Now.Dot][nw] = Dis[Now.Dot][Now.WZ] + 1;
if(!Inq[Now.Dot][nw]) Inq[Now.Dot][nw] = 1, Q.push((Xjh){Now.Dot, nw});
}
}
}
int Ans = INF;
For(i, 1, M) Ans = min(Ans, Dis[N][i]);
if(Ans == INF) puts("-1"); else printf("%d\n", Ans);
return 0;
}