5 1 5 3 3 1 2 5 0
3
#include <cstdio>
#include <deque>
#define MAX 210
#define INF 1000000000
using namespace std ;
int graph[MAX][MAX] ;
int t[MAX] ;
bool visited[MAX] ;
int SPFA(int s , int d , int n)
{
int dis[MAX] , c[MAX];
for(int i = 1 ; i <= n ; ++i)
{
dis[i] = INF ;
c[i] = 0 ;
visited[i] = false ;
}
dis[s] = 0 ;
deque<int> que ;
que.push_front(s) ;
while(!que.empty())
{
int k = que.front() ;
que.pop_front() ;
visited[k] = false ;
c[k]++ ;
if(c[k]>n)
{
return -1 ;
}
for(int i = 1 ; i <= n ; ++i)
{
if(dis[i]>dis[k]+graph[k][i])
{
dis[i] = dis[k]+graph[k][i] ;
visited[i] = true ;
if(!que.empty())
{
if(que.front()<=dis[i])
que.push_back(i) ;
else
que.push_front(i) ;
}
else
{
que.push_front(i) ;
}
}
}
}
return dis[d] ;
}
int main()
{
int n , a , b ;
while(~scanf("%d",&n) && n)
{
scanf("%d%d",&a,&b) ;
for(int i = 1 ; i <= n ; ++i)
{
scanf("%d",&t[i]) ;
}
for(int i = 0 ; i <= n ; ++i)
{
for(int j = 0 ; j <= n ; ++j)
{
graph[i][j] = INF ;
}
}
for(int i = 1 ; i <= n ; ++i)
{
if(i+t[i]<=n)
{
graph[i][i+t[i]] = 1 ;
}
if(i-t[i]>0)
{
graph[i][i-t[i]] = 1 ;
}
}
if(b<1|b>n)
{
puts("-1") ;
continue ;
}
int ans = SPFA(a,b,n) ;
if(ans >= INF)
puts("-1") ;
else
printf("%d\n",ans) ;
}
return 0 ;
}#include <stdio.h>
#define MAX 210
#define INF 1000000000
int graph[MAX][MAX] ;
int t[MAX] , dis[MAX];
bool visited[MAX] ;
void dijkstra(int s , int n)
{
for(int i = 1 ; i <= n ; ++i)
{
dis[i] = graph[s][i] ;
visited[i] = false ;
}
dis[s] = 0 ; //忘了写这行代码。。让我wrong成SB了
visited[s] = true ;
for(int i = 1 ; i < n ; ++i)
{
int index = -1 , min = INF;
for(int j = 1 ; j <= n ; ++j)
{
if(!visited[j] && dis[j]<min)
{
index = j ;
min = dis[j] ;
}
}
if(index == -1)
{
return ;
}
visited[index] = true ;
for(int j = 1 ; j <= n ; ++j)
{
if(!visited[j] && dis[j]>dis[index]+graph[index][j])
{
dis[j] = dis[index]+graph[index][j] ;
}
}
}
}
int main()
{
int n , a , b ;
while(~scanf("%d",&n) && n)
{
scanf("%d%d",&a,&b) ;
for(int i = 1 ; i <= n ; ++i)
{
scanf("%d",&t[i]) ;
}
for(int i = 0 ; i <= n ; ++i)
{
for(int j = 0 ; j <= n ; ++j)
{
graph[i][j] = INF ;
}
}
for(int i = 1 ; i <= n ; ++i)
{
if(i+t[i]<=n)
{
graph[i][i+t[i]] = 1 ;
}
if(i-t[i]>0)
{
graph[i][i-t[i]] = 1 ;
}
}
if(b<1|b>n)
{
puts("-1") ;
continue ;
}
dijkstra(a,n) ;
if(dis[b] >= INF)
puts("-1") ;
else
printf("%d\n",dis[b]) ;
}
return 0 ;
}hdu 1548 A strange lift Dijkstra+SPFA算法AC
原文:http://blog.csdn.net/lionel_d/article/details/44701901