#include<cstdio> #include<iostream> #include<cstring> #include<cmath> using namespace std; double x[110],y[110],dis[101],a[101][101]; bool v[101]; int n,m,xx,yy,st,ed; int q[10000]; inline double calc(int i,int j){ return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); } void spfa(){ memset(v,0,sizeof(v)); for(int i=1;i<=n;++i) dis[i]=99999999.0; int l=1,r=1; q[1]=st; dis[st]=0; v[st]=true; while (l<=r){ int x=q[l++]; v[x]=false; for(int i=1;i<=n;++i) if (i!=x && a[x][i]<0x7fffffff) if (dis[i]>dis[x]+a[x][i]){ dis[i]=dis[x]+a[x][i]; if (!v[i]){ v[i]=true; q[++r]=i; } } } } int main(){ cin>>n; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[i][j]=0x7fffffff; for(int i=1;i<=n;++i) a[i][i]=0; for(int i=1;i<=n;++i) scanf("%lf%lf",&x[i],&y[i]); cin>>m; for(int i=1;i<=m;++i){ scanf("%d%d",&xx,&yy); if (xx!=yy) a[xx][yy]=a[yy][xx]=calc(xx,yy); } cin>>st>>ed; spfa(); printf("%0.2lf",dis[ed]); return 0; } /************************************************************** Problem: 2049 User: admin Language: C++ Result: Accepted Time:26 ms Memory:2200 kb ****************************************************************/