记录编号	228720	评测结果	AAAAA
题目名称	[省常中2011S4] 最短路径问题	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2016-02-19 15:26:10	内存使用	0.41 MiB

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<stack>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=110;
struct Shu
{
	int x,y;
};
int n,e,qi,zhi;
double a[maxn][maxn],dis[maxn];
bool flag[maxn];
void Init();
void Dijs(int );
int main()
{
    freopen("short.in","r",stdin);
	freopen("short.out","w",stdout);
	Init();
	printf("%.2lf",dis[zhi]);
	return 0;
}
void Init()
{
	Shu s[maxn];
	memset(a,0,sizeof(a));
	memset(flag,0,sizeof(flag));
	memset(dis,0x7f,sizeof(dis));
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i].x>>s[i].y;
	}
	cin>>e;
	for(int i=1;i<=e;i++)
	{
		double z;
		int z1,z2;
		cin>>z1>>z2;
		z=sqrt((s[z1].x-s[z2].x)*(s[z1].x-s[z2].x)+(s[z1].y-s[z2].y)*(s[z1].y-s[z2].y));
		a[z1][z2]=a[z2][z1]=z;
	}
	cin>>qi>>zhi;
	Dijs(qi);
}
void Dijs(int x)
{
	flag[x]=1;dis[x]=0;
	for(int i=1;i<=n;i++)
	{
		if(a[x][i]!=0)dis[i]=a[x][i];
	}
	for(int i=2;i<=n;i++)
	{
		int k,temp=0x7f7f7f7f;
		for(int j=1;j<=n;j++)
		{
			if(!flag[j] && dis[j]<temp)
			{
				temp=dis[j];
				k=j;
			}
		}
		flag[k]=1;
		for(int j=1;j<=n;j++)
		{
			if(a[k][j]!=0&&dis[j]>a[k][j]+dis[k])
			{
				dis[j]=a[k][j]+dis[k];
			}
		}
	}
}