样例未过,求调
查看原帖
样例未过,求调
1271339
Lukas_gaoxi_yan楼主2024/10/19 16:53
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,x[110],y[110];
double a[1100][1100],d[110];
bool f[110];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	cin>>m;
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		a[u][v]=sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]));
		a[v][u]=a[u][v];
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			cout<<setw(16)<<a[i][j];
//		}
//		cout<<endl;
//	}
	cin>>s>>t;
	memset(d,0x3f,sizeof(d));
	for(int i=1;i<=n;i++){
	 	int mi=-1;
	 	for(int j=1;j<=n;j++){
	 		if(!f[j]&&(mi==-1||d[j]<d[mi])){
	 			mi=j;
			 }
		 }
		 f[mi]=true;
		 for(int j=1;j<=n;j++){
		 	if(!f[j]&&a[mi][j]!=0&&d[mi]+a[mi][j]<d[j]){
			 d[j]=d[mi]+a[mi][j]; 
			 }
		 } 
	 }
	cout<<d[t];
	return 0;
} 


2024/10/19 16:53
加载中...