Metal Steak

Hard to eat

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

公告

aaaaaaaaaaaa

常用链接

留言簿(1)

我参与的团队

搜索

  •  

最新评论

#include <iostream>
#include 
<math.h>
#include 
<iomanip>
using namespace std;

int    n, m;
int    s, t;
double map[101][101];

struct
coordinate
{
    
int    x;
    
int    y;
    coordinate()
    {
        x 
= y = 0;
    }
}c[
101];

void
__read__()
{

    cin 
>> n;
    
forint i = 1; i <= n; i++ )
        
forint j = 1; j <= n; j++ )
            map[i][j] 
= 999999;
    
forint i = 1; i <= n; i++ )
        cin 
>> c[i].x >> c[i].y;
    cin 
>> m;
    
forint i = 1; i <= m; i++ )
    {
        
int p, q;
        cin 
>> p >> q;
        map[q][p] 
= map[p][q] = sqrt( ( c[p].x - c[q].x ) * ( c[p].x - c[q].x )
                        
+ ( c[p].y - c[q].y ) * ( c[p].y - c[q].y ) );
    }
    cin 
>> s >> t;
}

void
__floyd__()
{
    
forint k = 1; k <= n; k++ )
        
forint i = 1; i <= n; i++ )
            
forint j = 1; j <= n; j++ )
                
if( i != j && i != k && j != k )
                    
if( map[i][j] > map[i][k] + map[k][j] )
                        map[i][j] 
= map[i][k] + map[k][j];
}

void
__outp__()
{
    cout 
<< setiosflags( ios::fixed ) << setprecision( 2 )
         
<< map[s][t] << endl;
}

int
main()
{
    __read__();
    __floyd__();
    __outp__();

    
return 0;
}

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

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