比赛 |
hhh |
评测结果 |
AAAAA |
题目名称 |
最短路径问题 |
最终得分 |
100 |
用户昵称 |
cool |
运行时间 |
0.003 s |
代码语言 |
C++ |
内存使用 |
0.43 MiB |
提交时间 |
2018-07-31 10:51:49 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iomanip>
using namespace std;
int a[101][101];
int m,n,s,t,x,y,i,k,j,e;
double f[101][101];
int main()
{
freopen("short.in","r",stdin);
freopen("short.out","w",stdout);
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i][1]>>a[i][2];
cin>>m;
memset(f,0x7f,sizeof(f));
for(i=1;i<=m;i++)
{
cin>>x>>y;
f[x][y]=f[y][x]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));
}
cin>>s>>e;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if((i!=j)&&(i!=k)&&(j!=k)&&(f[i][k]+f[k][j]<f[i][j]))
f[i][j]=f[i][k]+f[j][k];
cout<<setiosflags(ios::fixed)<<setprecision(2)<<f[s][e]<<endl;
return 0;
}