记录编号	50692	评测结果	AAAAA
题目名称	[省常中2011S4] 最短路径问题	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2012-11-28 20:28:17	内存使用	0.40 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;
const double MAX=0xffffff;
double c[101][101]={0},point[101][2]={0},f[101]={0};//c为路程,point为点,f为到当前最短路
bool used[101]={0};
int n,m,s,t;//n为顶点数,s起点t终点
void Dijkstra(void){
	int i,sum,min=-1;
	for(i=1;i<=n;i++) f[i]=c[s][i];
	used[s]=1,sum=1;
	while(sum<n){
		min=-1;
		for(i=1;i<=n;i++){
			if(used[i]) continue;
			if(min==-1||f[i]<f[min]) min=i;
		}
		if(min==-1) break;
		sum++;
		used[min]=1;
		for(i=1;i<=n;i++){
			if(used[i]) continue;
			if(f[min]+c[min][i]<f[i]) f[i]=f[min]+c[min][i];
		}
	}
}
int main(){
	freopen("short.in","r",stdin);
	freopen("short.out","w",stdout);
	cout<<setiosflags(ios::fixed)<<setprecision(2);
	scanf("%d",&n);
	int i,j,k;
	double x,y;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(i==j) continue;
			c[i][j]=MAX;
		}
	}
	for(i=1;i<=n;i++) scanf("%lf%lf",&point[i][0],&point[i][1]);
	scanf("%d",&m);
	for(k=0;k<m;k++){
		scanf("%d%d",&i,&j);
		x=point[i][0]-point[j][0],y=point[i][1]-point[j][1];
		c[i][j]=sqrt(x*x+y*y),c[j][i]=c[i][j];
	}
	scanf("%d%d",&s,&t);
	Dijkstra();
	cout<<f[t]<<endl;
	return 0;
}