AcWing 384. 升降梯上
原题链接
简单
作者:
M_Fish
,
2019-08-24 10:41:59
,
所有人可见
,
阅读 916
#include<bits/stdc++.h>
#define re register int
using namespace std;
int n,m,wzz,zt[1005],vis[1005],c[25],dis[1005];
vector<int>Edge[1005];
int read()
{
int ans=0;
char w=' ',ch=getchar();
while(ch<'0' || ch>'9')
{
w=ch;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
ans=(ans<<3)+(ans<<1);
ans+=ch-'0';
ch=getchar();
}
return (w=='-'?-ans:ans);
}
int calc(int x,int y)
{
int d=y-x,ans=0,bj=0;
for(re i=1;i<=m;i++)
{
if(c[i]==d)
{
wzz=i;
ans+=abs(zt[x]-i);
bj=1;
break;
}
}
if(bj==1)
{
ans+=2*abs(y-x);
}
else
{
ans=999999999;
}
return ans;
}
void SPFA()
{
queue<int>q;
for(re i=1;i<=n;i++)
{
dis[i]=999999999;
}
dis[1]=0;
q.push(1);
vis[1]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(re j=0;j<Edge[u].size();j++)
{
int v=Edge[u][j],sum=calc(u,v);
if(dis[v]>dis[u]+sum)
{
dis[v]=dis[u]+sum;
zt[v]=wzz;
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
return;
}
int main()
{
freopen("updown.in","r",stdin);
freopen("updown.out","w",stdout);
n=read();m=read();
for(re i=1;i<=m;i++)
{
c[i]=read();
if(c[i]==0)
{
zt[1]=i;
}
}
for(re i=1;i<=n;i++)
{
for(re j=i+1;j<=n;j++)
{
Edge[i].push_back(j);
Edge[j].push_back(i);
}
}
SPFA();
if(dis[n]==999999999) cout<<-1;
else cout<<dis[n];
}
头像好评