记录编号	154755	评测结果	AAAAA
题目名称	[省常中2011S4] 最短路径问题	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	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;
}