记录编号 154755 评测结果 AAAAA
题目名称 [省常中2011S4] 最短路径问题 最终得分 100
用户昵称 Gravatar一個人的雨 是否通过 通过
代码语言 C++ 运行时间 0.008 s
提交时间 2015-03-24 19:00:59 内存使用 4.14 MiB
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
using namespace std;
int n,s,t,m;
int a[1000],b[1000];
float g[1000][1000];
int main()
{
 freopen("short.in","r",stdin);
 freopen("short.out","w",stdout);
 cin>>n;
 for (int i=1;i<=n;++i)
  {
  	int x,y;
  	cin>>x>>y;
	a[i]=x;
	b[i]=y; 
  }
 for (int i=1;i<=n;++i)
  for (int j=1;j<=n;++j)
   g[i][j]=100000000;
 cin>>m;
 for (int i=1;i<=m;++i)
  {
  	int x,y;
	cin>>x>>y;
	g[x][y]=g[y][x]=sqrt((a[x]-a[y])*(a[x]-a[y])+(b[x]-b[y])*(b[x]-b[y]));   
  }
 cin>>s>>t;
 for (int k=1;k<=n;++k)
  for (int i=1;i<=n;++i)
   if (i!=k)
    for (int j=1;j<=n;++j)
     if (g[i][k]+g[k][j]<g[i][j])
      g[i][j]=g[i][k]+g[k][j];
 printf("%.2f",g[s][t]);
 return 0;
}