显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=110,maxm=maxn*maxn;
double Bellman_Ford(int,int);
int n,m,x[maxn],y[maxn],s[maxm],t[maxm],a,b;
double dis[maxn],d[maxm];
inline int MAIN(){
#define MINE
#ifdef MINE
freopen("short.in","r",stdin);
freopen("short.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
s[i]=t[i+m]=a;
t[i]=s[i+m]=b;
d[i]=d[i+m]=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
scanf("%d%d",&a,&b);
printf("%.2lf",Bellman_Ford(a,b));
return 0;
}
inline double Bellman_Ford(int x,int y){
for(int i=1;i<=n;i++)dis[i]=1e50;
dis[x]=0.0;
for(int k=1;k<n;k++)for(int i=1;i<=(m<<1);i++)
dis[t[i]]=min(dis[t[i]],dis[s[i]]+d[i]);
return dis[y];
}
int hzoier=MAIN();
int main(){;}