其实我刚开始题读错了，才导致我写图论。。。
spfa跑最短路，开一个node记录状态（pair当然滋磁）：所在楼层和槽的位置
以层数为1，槽在0的位置 为初始状态并进队，向每一个合法位置扩展，跑spfa，直到收敛。
#include<cstdio> #include<iostream> #include<queue> #include<cstring> #include<cmath> #define R register int using namespace std; inline int g() { R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix; } struct node{ int u,pos; node() {} node(int uu,int ppos):u(uu),pos(ppos) {} }e[1010]; queue<node>q; bool vis[1010][24]; int n,m,z,ans=0x3f3f3f3f,d[1010][24],a[24]; inline void spafa() { memset(d,0x3f,sizeof(d)); q.push(node(1,z)); vis[1][z]=true,d[1][z]=0; while(q.size()) { R u=q.front().u,pos=q.front().pos; q.pop(); vis[u][pos]=false; for(R i=1;i<=m;++i) { if(u+a[i]<=0) continue; if(u+a[i]>n) break; if(d[u+a[i]][i]>d[u][pos]+abs(i-pos)+abs(a[i])*2) { d[u+a[i]][i]=d[u][pos]+abs(i-pos)+abs(a[i])*2; if(vis[u+a[i]][i]) continue; vis[u+a[i]][i]=true; q.push(node(u+a[i],i)); } } } } signed main() { freopen("up.in","r",stdin); freopen("up.out","w",stdout); n=g(),m=g(); for(R i=1;i<=m;++i) {a[i]=g(); if(!a[i]) z=i;} spafa(); for(R i=1;i<=m;++i) ans=min(ans,d[n][i]); if(ans==0x3f3f3f3f) printf("-1 "); else printf("%d",ans); }
2019.04.11