Metal Steak

Hard to eat

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  0 Posts :: 79 Stories :: 0 Comments :: 0 Trackbacks

公告

aaaaaaaaaaaa

常用链接

留言簿(1)

我参与的团队

搜索

  •  

最新评论

#include <iostream>
using namespace std;

int
elevator[
201], g[201][201], n, source, target, mp;

struct
dijkstra
{
    
int
    to, wei;
    dijkstra()
    {
        to 
= wei = 0;
    }
}d[
1001];

void
__read__()
{
    cin 
>> n >> source >> target;
    
forint i = 1; i <= n; i++ )
        cin 
>> elevator[i];
}

void
__init__()
{
    
forint i = 1; i <= n; i++ )
        
forint j = 1; j <= n; j++ )
            g[i][j] 
= 99999;
    
forint i = 1; i <= n; i++ )
    {
        
if( i + elevator[i] <= n )
            g[i][i 
+ elevator[i]] = 1;
        
if( i - elevator[i] > 0 )
            g[i][i 
- elevator[i]] = 1;
    }
    
forint i = 0; i < n; i++ )
    {
        d[i].to 
= i + 1;
        d[i].wei 
= g[source][i + 1];
    }
    
if( source != 1 )
        swap( d[
0], d[source - 1] );
}

void
findmin( 
int x )
{
    
int min = d[x].wei;
    mp 
= x;
    
forint i = x; i < n; i++ )
        
if( d[i].wei < min )
        {
            mp 
= i;
            min 
= d[i].wei;
        }
}

void
swap( dijkstra 
&d1, dijkstra &d2 )
{
    dijkstra d3 
= d1;
    d1 
= d2;
    d2 
= d3;
}

void
__dijkstra__( 
int x )
{
    
if( x < n - 1 )
    {
        
forint i = x + 1; i < n; i++ )
            
if( d[x].wei + g[d[x].to][d[i].to] < d[i].wei )
                d[i].wei 
= d[x].wei + g[d[x].to][d[i].to];

        findmin( x 
+ 1 );
        
if( mp )
            swap( d[x 
+ 1], d[mp] );

        
if( d[x + 1].to == target )
        {
            
if( d[x + 1].wei == 99999 )
                cout 
<< "-1" << endl;
            
else
                cout 
<< d[x + 1].wei << endl;
            exit( 
0 );
        }
        __dijkstra__( x 
+ 1 );
    }
}

int
main()
{
    __read__();
    
if( source == target )
    {
        cout 
<< "0" << endl;
        
return 0;
    }
    __init__();
    __dijkstra__( 
0 );
    
    
return 0;
}

posted on 2009-09-15 21:49 mad4alcohol 阅读(240) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理