首页 > 代码库 > 【最短路】【spfa】小vijos P1447 Updown
【最短路】【spfa】小vijos P1447 Updown
小vijos P1447 Updown
背景
开启了升降梯的动力之后，探险队员们进入了升降梯运行的那条竖直的隧道，映入眼帘
的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手
柄。
faebdc 之塔一共有 N 层，升降梯在每层都有一个停靠点。手柄有 M 个控制槽，第 i
个控制槽旁边标着一个数 Ci， 满足 C1<C2<C3<...<CM。 如果 Ci>0，表示手柄扳动到该槽
时，电梯将上升 Ci 层；如果 Ci<0，表示手柄扳动到该槽时，电梯将下降|Ci| 层；并且一定
存在一个 Ci=0，手柄最初就位于此槽中。注意升降梯只能在 1~N 层间移动，因此扳动到使
升降梯移动到 1 层以下、N 层以上的控制槽是不允许的。
电梯每移动一层，需要花费 2 秒钟时间，而手柄从一个控制槽扳到相邻的槽， 需要花费
1 秒钟时间。探险队员现在在 1 层，并且想尽快到达 N 层，他们想知道从 1 层到 N 层至少
需要多长时间？
输入格式
第一行两个正整数 N、M
第二行 M 个整数 C1、C2...CM
输出格式
输出一个整数表示答案，即至少需要多长时间。若不可能到达输出-1。
样例输入
6 3
-1 0 2
样例输出
19
时间限制
各个测试点1s
注释
样例说明
手柄从第二个槽扳到第三个槽(0 扳到 2)，用时 1 秒，电梯上升到 3 层，用时 4 秒。
手柄在第三个槽不动，电梯再上升到 5 层，用时 4 秒。
手柄扳动到第一个槽(2 扳到-1)，用时 2 秒，电梯下降到 4 层，用时 2 秒。
手柄扳动到第三个槽(-1 扳倒 2)，用时 2 秒，电梯上升到 6 层，用时 4 秒。
总用时为(1+4)+4+(2+2)+(2+4)=19 秒。
数据范围与约定
对于 30% 的数据，满足 1≤N≤10，2<=M<=5。
对于 100% 的数据，满足 1≤N≤1000，2<=M<=20，-N<C1<C2<...<CM<N
显然根据题意，可以dp，但是我们很难转移，所以，我们把所有状态当成点，建边，跑最短路即可。
1 #include<cstdio> 2 #include<algorithm> 3 #include<queue> 4 #include<cstring> 5 using namespace std; 6 #define M 400001 7 #define N 25001 8 queue<int>q; 9 int n,m,a[21],en,v[M],w[M],first[M],next[M],num[1001][21],sta,ans=2147483647,dis[N];10 bool inq[N];11 int Abs(const int &x){return x<0 ? (-x) : x;}12 void AddEdge(const int &U,const int &V,const int &W)13 {14 v[++en]=V;15 w[en]=W;16 next[en]=first[U];17 first[U]=en;18 }19 void spfa(const int &s)20 {21 memset(dis,0x7f,sizeof(dis));22 q.push(s); inq[s]=1; dis[s]=0;23 while(!q.empty())24 {25 int U=q.front();26 for(int i=first[U];i;i=next[i])27 if(dis[v[i]]>dis[U]+w[i])28 {29 dis[v[i]]=dis[U]+w[i];30 if(!inq[v[i]])31 {32 inq[v[i]]=1;33 q.push(v[i]);34 }35 }36 q.pop(); inq[U]=0;37 }38 }39 int main()40 {41 scanf("%d%d",&n,&m);42 for(int i=1;i<=m;i++) scanf("%d",&a[i]);43 for(int i=1;i<=n;i++)44 for(int j=1;j<=m;j++)45 {46 num[i][j]=++en;47 if(i==1&&a[j]==0) sta=en;48 } en=0;49 for(int i=1;i<=n;i++)50 for(int j=1;j<=m;j++)//单层移动手柄51 for(int k=1;k<=m;k++)52 if(j!=k)53 AddEdge(num[i][j],num[i][k],Abs(j-k));54 for(int i=1;i<=n;i++)55 for(int j=1;j<=m;j++)56 if(a[j]!=0&&i+a[j]>=1&&i+a[j]<=n)57 AddEdge(num[i][j],num[i+a[j]][j],(Abs(a[j])<<1));58 spfa(sta);59 for(int i=1;i<=m;i++) ans=min(ans,dis[num[n][i]]);60 printf("%d\n",ans>=2000000000 ? -1 : ans);61 return 0;62 }
【最短路】【spfa】小vijos P1447 Updown