HDU 1548 A strange lift(dij+邻接矩阵)

( ̄▽ ̄)"

//dijkstra算法,
//只是有效边(即能从i楼到j楼)的边权都为1(代表次数1);
//关于能否到达目标楼层b,只需判断最终lowtime[b]是否等于INF即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int INF=10e7;
const int MAXN=210;
int k,minn;
int K[MAXN];
int cost[MAXN][MAXN];
int lowtime[MAXN];
bool vis[MAXN]; void dij(int n,int start)
{
for(int i=1;i<=n;i++)
{
lowtime[i]=INF;vis[i]=0;
}
lowtime[start]=0;
for(int i=1;i<=n;i++)
{
k=-1,minn=INF;
for(int i=1;i<=n;i++)
{
if(!vis[i]&&lowtime[i]<minn)
{minn=lowtime[i];k=i;}
}
if(k==-1) break;
vis[k]=1;
for(int i=1;i<=n;i++)
{
if(!vis[i]&&cost[k][i]>=0&&lowtime[k]+cost[k][i]<lowtime[i])
{
lowtime[i]=lowtime[k]+cost[k][i];
}
}
}
} int main()
{
int n,m,a,b;
while(scanf("%d",&n)&&n!=0)
{
scanf("%d%d",&a,&b);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cost[i][j]=cost[j][i]=INF;
for(int i=1;i<=n;i++)
{
scanf("%d",&K[i]);
if(i+K[i]<=n)
cost[i][i+K[i]]=1;
if(i-K[i]>=1)
cost[i][i-K[i]]=1;
}
dij(n,a);
if(lowtime[b]==INF)
printf("-1\n");
else
printf("%d\n",lowtime[b]);
}
return 0;
}
上一篇:poj 2533 Longest Ordered Subsequence(dp)


下一篇:阿里云centos7[linux]安装nginx