HDU 1548 A strange lift(dij+邻接矩阵)
2024-08-26 22:59:10
//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;
}
最新文章
- java中的锁
- js杂项
- Web开发中管理ipad屏幕的方向变化
- JAVA中最常用的十个快捷键
- SQL Server 事务
- android 根据包名打开app程序
- POJ 2349 Arctic Network(最小生成树,第k大边权,基础)
- 【贪心】Vijos P1615 旅行
- 在动态引用DLL-A中,当参数是个实体,而实体的属性在另一个DLL-B中。。我们需要得到A这个实体并将其赋值,并将赋值的实体传人DLL-A的方法中。
- jquery fadeIn用法
- Python的字符编码
- MyEclipse 的智能提示设置 使开发写代码的速度更快
- varnish 相关说明
- sublime使用技巧总结
- os模块。笔记
- 应收事物处理删除 SQL 语句
- windows本地启动tomcat闪退
- 今天练手了下mysqlbinlog,标记下
- Objective-C:MRC手动释放对象内存举例(引用计数器)
- Sublime Text 3 插件的安装、升级和卸载