记录编号	216468	评测结果	AAAAA
题目名称	[省常中2011S4] 最短路径问题	最终得分	100
用户昵称	NVIDIA	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-12-29 09:58:03	内存使用	0.38 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int k,s,e,n,m,x[105],y[105];
double min,d[105],f[105][105];
double max=1e30;
bool b[105];
int main()
{
	freopen("short.in","r",stdin);
	freopen("short.out","w",stdout);
	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<=n;i++)
	for(int j=1;j<=n;j++)
	f[i][j]=max;
	for(int i=1;i<=m;i++)
	{
		int xx,yy;
		scanf("%d%d",&xx,&yy);
		f[xx][yy]=f[yy][xx]=sqrt(pow(double(x[xx]-x[yy]),2)+pow(double(y[xx]-y[yy]),2));
	}
	scanf("%d%d",&s,&e);
	for(int i=1;i<=n;i++) d[i]=f[s][i];
	memset(b,false,sizeof(b));
	b[s]=true;
	d[s]=0;
	for(int i=1;i<=n-1;i++)
	{
		min=max;
		k=0;
		for(int j=1;j<=n;j++)
		if((!b[j])&&(d[j]<min))
		{
			min=d[j];
			k=j;
		}
		if (k==0) break;
		b[k]=true;
		for(int j=1;j<=n;j++)
		if(d[k]+f[k][j]<d[j])
		d[j]=d[k]+f[k][j];
	}
	printf("%.2lf",d[e]);
	return 0;
}