记录编号	291166	评测结果	AAAAA
题目名称	1075.[省常中2011S4] 最短路径问题	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-08-07 11:20:24	内存使用	0.00 MiB

#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(){;}