集合位置 60分求调

#include<bits/stdc++.h>
using namespace std;
int n,m;
double a[210][210];
double dis[10109],x[10010],y[10010];
int vis[10010],pre[10010],d[10109],k;
int s,t;
void output(int x){
	if(pre[x]==0){
		k++;
		d[k]=x;
//		cout<<x;
		return ;
	}
	output(pre[x]);
	k++;
	d[k]=x;
//	cout<<" "<<x;
}
double jc(double x,double y,double x2,double y2){
	return sqrt((x-x2)*(x-x2)+(y-y2)*(y-y2));
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		a[u][v]=jc(x[u],y[u],x[v],y[v]);
		a[v][u]=jc(x[u],y[u],x[v],y[v]);
	}
	for(int i=1;i<=n;i++){
		dis[i]=0x3f3f3f3f;;
	}
	s=1,t=n;
	dis[s]=0;
	for(int i=1;i<=n;i++){
		int x=0;
		for(int j=1;j<=n;j++){
			if(vis[j]==0&&(x==0||dis[j]<dis[x])){
				x=j;
			}
		}
		vis[x]=1;
		for(int j=1;j<=n;j++){
			if(a[x][j]!=0){
				if(dis[j]>dis[x]+a[x][j]){
					dis[j]=dis[x]+a[x][j];
					pre[j]=x;
				}
			}
		}
	}
//	for(int i=1;i<=n;i++){
//		cout<<pre[i]<<endl;
//	}
	output(t); 
//	cout<<endl;
//	for(int i=1;i<=k;i++){
//		cout<<d[i]<<endl;
//	}
//	cout<<endl<<k<<endl;
	double mi=INT_MAX;
	memset(vis,0,sizeof(vis));
	for(int j=2;j<=k;j++){
		for(int i=1;i<=n;i++){
			dis[i]=INT_MAX;
		}
		s=1,t=n;
		dis[s]=0;
		a[d[j-1]][d[j]]=0;
		a[d[j]][d[j-1]]=0;
		for(int i=1;i<=n;i++){
			int x=0;
			for(int j=1;j<=n;j++){
				if(vis[j]==0&&(x==0||dis[j]<dis[x])){
					x=j;
				}
			}
			vis[x]=1;
			for(int j=1;j<=n;j++){
				if(a[x][j]!=0){
					if(dis[j]>dis[x]+a[x][j]){
						dis[j]=dis[x]+a[x][j];
						pre[j]=x;
					}
				}
			}
		}
	//	cout<<dis[t]<<endl;
		mi=min(mi,dis[t]);
		a[d[j-1]][d[j]]=1;
	}
	printf("%.2lf",mi);
}