`
从此醉
  • 浏览: 1034515 次
  • 性别: Icon_minigender_1
  • 来自: US
社区版块
存档分类
最新评论

hdu 1548 A strange lift

 
阅读更多

点击打开链接hdu 1548


思路:最短路+Dijkstra
分析:数据量不大直接Dijkstra即可,但是注意要把图处理成有向图,因为题目中的电梯是有分上下两个分向的。


代码:


#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 210
#define INF 0xFFFFFFF

int n , A , B;
int value[MAXN][MAXN];
int dis[MAXN];
int vis[MAXN];

void Dijkstra(int s){
    int pos;
    memset(vis , 0 , sizeof(vis));
    for(int i = 1 ; i <= n ; i++)
       dis[i] = INF;
    dis[s] = 0;
    for(int i = 1 ; i <= n ; i++){
       pos = -1;
       for(int j = 1 ; j <= n ; j++){
          if(!vis[j] && (pos == -1 || dis[j] < dis[pos]))
            pos = j;
       }
       vis[pos] = 1;
       for(int j = 1 ; j <= n ; j++){
          if(!vis[j] && dis[j] > dis[pos] + value[pos][j])
            dis[j] = dis[pos] + value[pos][j];
       }
    }
}

int main(){
   int k;
   while(scanf("%d" , &n) &&n){
      scanf("%d%d" , &A , &B);
      for(int i = 1 ; i <= n ; i++){
         for(int j = 1 ; j <= n ; j++)
            value[i][j] = INF;
      }
      for(int i = 1 ; i <= n ; i++){
         scanf("%d" , &k);
         /*处理成有向图*/
         if(i-k >= 1)
           value[i][i-k] = 1;
         if(i+k <= n)
           value[i][i+k] = 1;
      } 
      Dijkstra(A);
      if(dis[B] != INF)
        printf("%d\n" , dis[B]);
      else
        printf("-1\n");
   }
   return 0;
}




分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics