比赛 hhh 评测结果 AAAAA
题目名称 最短路径问题 最终得分 100
用户昵称 梦那边的美好ET 运行时间 0.005 s
代码语言 C++ 内存使用 0.39 MiB
提交时间 2018-07-31 10:16:21
显示代码纯文本
#include<iostream>  
#include<cstdio>
#include<cmath>
#include<cstring>  
#include<algorithm>  
using namespace std; 
double mp[101][101];
int n,a[101],b[101],a1,a2,m;
int main(){ 
    freopen("short.in","r",stdin);        
    freopen("short.out","w",stdout);      
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i]>>b[i];
	}
	for(int i=1;i<=n;++i)
	    for(int j=1;j<=n;++j)
	        if(i!=j)
	            mp[i][j]=9999999;
	cin>>m;
	for(int i=1;i<=m;++i){
		cin>>a1>>a2;
		mp[a1][a2]=sqrt((a[a1]-a[a2])*(a[a1]-a[a2])+(b[a1]-b[a2])*(b[a1]-b[a2]));
		mp[a2][a1]=sqrt((a[a1]-a[a2])*(a[a1]-a[a2])+(b[a1]-b[a2])*(b[a1]-b[a2]));		
	}
	cin>>a1>>a2;
	for(int k=1;k<=n;++k)
	    for(int i=1;i<=n;++i)
	        for(int j=1;j<=n;++j)
	            mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
	printf("%.2f",mp[a1][a2]);
    return 0;  
}