基础单源最短路径

 1 //hdu 1548
 2 #include<stdio.h>
 3 #include<string.h>
 4 #define INF 999999
 5 int map[202][202],vis[202],dist[202],pre[202];
 6 int n,a,b;
 7 void dijkstra(int s)
 8 {
 9     for(int i=1;i<=n;i++)
10     {
11         vis[i]=0;
12         dist[i]=map[s][i];
13         pre[i]=s;
14     }
15     vis[s]=1;
16     dist[s]=0;
17     for(int i=1;i<n;i++)
18     {
19         int p=0,min=100000000;
20         for(int j=1;j<=n;j++)
21             if(!vis[j]&&dist[j]<min)
22         {
23             min=dist[j];
24             p=j;
25         }
26      vis[p]=1;
27     if(p==0)  return;
28     for(int j=1;j<=n;j++)
29         if(!vis[j]&&map[p][j]+dist[p]<dist[j])
30            {
31                dist[j]=map[p][j]+dist[p];
32                pre[j]=p;
33            }
34     }
35 
36 }
37 int main()
38 {
39     //freopen("in.txt","r",stdin);
40     while(scanf("%d",&n)!=EOF&&n)
41     {
42         int k[500];
43         scanf("%d%d",&a,&b);
44         memset(map,INF,sizeof(map));
45         for(int i=1;i<=n;i++)
46         {
47             scanf("%d",&k[i]);
48             if(i+k[i]<=n)
49                 map[i][i+k[i]]=1;
50              if(i-k[i]>0)
51                 map[i][i-k[i]]=1;
52         }
53         dijkstra(a);
54         if(dist[b]>INF)
55             printf("-1\n");
56         else
57             printf("%d\n",dist[b]);
58     }
59     return 0;
60 }