hdu 1548 升降梯

题目大意：有一个升降机，它有两个按钮UP和DOWN，给你一些数i表示层数，并且每层对应的Ki，如果按UP按钮，会从第i层升到第i+Ki层；如果按了DOWN则会从第i层降到第i-Ki层；并规定能到的层数为1到N，现在的要求就是给你N,A,B和一串数K1到Kn，问你从A到B，至少按几下按钮。

构造一个图，边的权值为1

Sample Input
5 1 5 //层数起点终点
3 3 1 2 5
0

Sample Output
3

Dijkstra：（O（n^2））

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # define LL long long
 7 using namespace std ;
 8 
 9 const int MAXN=300;
10 const int INF=0x3f3f3f3f;
11 int n ;
12 bool vis[MAXN];
13 int cost[MAXN][MAXN] ;
14 int lowcost[MAXN] ;
15 int pre[MAXN];
16 void Dijkstra(int beg)
17 {
18     for(int i=0;i<n;i++)
19     {
20         lowcost[i]=INF;vis[i]=false;pre[i]=-1;
21     }
22     lowcost[beg]=0;
23     for(int j=0;j<n;j++)
24     {
25         int k=-1;
26         int Min=INF;
27         for(int i=0;i<n;i++)
28             if(!vis[i]&&lowcost[i]<Min)
29             {
30                 Min=lowcost[i];
31                 k=i;
32             }
33             if(k==-1)
34                 break ;
35             vis[k]=true;
36             for(int i=0;i<n;i++)
37                 if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])
38                 {
39                     lowcost[i]=lowcost[k]+cost[k][i];
40                         pre[i]=k;
41                 }
42     }
43 
44 }
45 
46 
47 
48 int main ()
49 {
50    // freopen("in.txt","r",stdin) ;
51 
52     while (scanf("%d" , &n ) !=EOF)
53     {
54         if (n==0)
55             break ;
56         int i , j ;
57         for (i = 0 ; i < n ; i++)
58             for (j = 0 ; j < n ; j++)
59                cost[i][j] = INF ;
60         int s , e , t;
61         scanf("%d %d" , &s , &e) ;
62         for (i = 0 ; i < n ; i++)
63         {
64             scanf("%d" , &t) ;
65             if (i + t <= n-1)
66                 cost[i][i+t] = 1 ;
67             if (i - t >= 0)
68                 cost[i][i-t] = 1 ;
69         }
70         Dijkstra(s-1) ;
71         if (lowcost[e-1] != INF)
72             printf("%d
" , lowcost[e-1]) ;
73         else
74             printf("-1
") ;
75     }
76 
77     return 0 ;
78 }

View Code

堆优化：

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # include <queue>
 7 # define LL long long
 8 using namespace std ;
 9 
10 const int INF=0x3f3f3f3f;
11 const int MAXN=300;
12 struct qnode
13 {
14     int v;
15     int c;
16     qnode(int _v=0,int _c=0):v(_v),c(_c){}
17     bool operator <(const qnode &r)const
18     {
19         return c>r.c;
20     }
21 };
22 struct Edge
23 {
24     int v,cost;
25     Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
26 };
27 vector<Edge>E[MAXN];
28 bool vis[MAXN];
29 int dist[MAXN];
30 int n ;
31 void Dijkstra(int start)//点的编号从1开始
32 {
33     memset(vis,false,sizeof(vis));
34     for(int i=1;i<=n;i++)dist[i]=INF;
35     priority_queue<qnode>que;
36     while(!que.empty())que.pop();
37     dist[start]=0;
38     que.push(qnode(start,0));
39     qnode tmp;
40     while(!que.empty())
41     {
42         tmp=que.top();
43         que.pop();
44         int u=tmp.v;
45         if(vis[u])continue;
46         vis[u]=true;
47         for(int i=0;i<E[u].size();i++)
48         {
49             int v=E[tmp.v][i].v;
50             int cost=E[u][i].cost;
51             if(!vis[v]&&dist[v]>dist[u]+cost)
52             {
53                 dist[v]=dist[u]+cost;
54                 que.push(qnode(v,dist[v]));
55             }
56         }
57     }
58 }
59 void addedge(int u,int v,int w)
60 {
61     E[u].push_back(Edge(v,w));
62 }
63 
64 int main ()
65 {
66   //  freopen("in.txt","r",stdin) ;
67     int m ;
68     while (scanf("%d" , &n) !=EOF)
69     {
70         if (n==0 )
71             break ;
72         int u , v , w ;
73         int i , j ;
74         for(i=1;i<=n;i++)
75             E[i].clear();
76 
77         int s , e , t;
78         scanf("%d %d" , &s , &e) ;
79         for (i = 1 ; i <= n ; i++)
80         {
81             scanf("%d" , &t) ;
82             if (i + t <= n)
83                 addedge(i,i+t,1) ;
84             if (i - t >= 1)
85                 addedge(i,i-t,1) ;
86         }
87         Dijkstra(s) ;
88         if (dist[e] != INF)
89             printf("%d
" , dist[e]) ;
90         else
91             printf("-1
") ;
92     }
93 
94     return 0 ;
95 }

View Code