又是一道典型的最短路径的题目,当然也可以用搜索,我现在在学习最短路径,所以就用Dijsktra来做的,一开始时WA了好几次,是因为这一题是应该抽象出来一个有向图,而我却是用了无向图,所以一直WA。最后改了一下,然后就过了。
#include <stdio.h>
#define DEBUG 1
const int N=300 ;
const int Max = 10000000 ;
int n, map[N][N], used[N], dis[N] ;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Dijkstra( int a, int b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i, j, index, min ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for( i=1; i<=n; ++i )
{
dis[i] = map[a][i] ;
used[i] = 0 ;
}
used[a] = 1 ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for( i=1; i<=n; ++i )
{
index = a ;
min = Max ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for( j=1; j<=n; ++j )
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if( !used[j] && min > dis[j] )
{
min = dis[j] ;
index = j ;
}
}
used[index] = 1 ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for( j=1; j<=n; ++j )
{
if( dis[j] > dis[index]+map[index][j] )
dis[j] = dis[index]+map[index][j] ;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if( dis[b] == Max )
{
//printf("%d\n", dis[b] ) ;
printf("-1\n") ;
}
else
printf("%d\n", dis[b] ) ;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main( )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
#if DEBUG
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
#endif
int i, j, a, b, temp ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while( scanf("%d", &n) && n )
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for( i=1; i<=n; ++i )
{
for( j=1; j<=n; ++j )
map[i][j] = Max ;
map[i][i] = 0 ;
}
scanf("%d%d", &a, &b ) ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for( i=1; i<=n; ++i )
{
scanf("%d", &temp ) ;
if( i - temp > 0 )
map[i][i-temp] = 1 ;
if( i + temp <= n )
map[i][i+temp] = 1 ;
}
Dijkstra( a, b ) ;
}
return 0 ;
}