记录编号	219170	评测结果	AAAAA
题目名称	[省常中2011S4] 最短路径问题	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-01-13 09:50:38	内存使用	1.17 MiB

#include<cstdio>
#include<cmath>
#include<cstring>
#define father(a) (a-1)>>1
#define lchild(a) (a<<1)+1
#define rchild(a) (a<<1)+2
using namespace std;
int x[101],y[101],n,m,s,t;
bool visited[101];
double ans[101];
struct edge{
	int v,next;
	double cost;
}lst[50000];//从lst[1]开始存边 
int start[101],last[101];
int tail=1;
void e_add(int a,int b,double w){
	if(start[a]==0){
		start[a]=last[a]=tail;
		lst[tail].v = b;
		lst[tail].cost = w;
		lst[tail].next = 0;
	}else{
		lst[last[a]].next = tail;
		last[a] = tail;
		lst[tail].v = b;
		lst[tail].cost = w;
		lst[tail].next = 0;
	}
	tail++;
}
struct node{
	int v1;
	double cost;
	node(int _v1=0,double _cost=0){
		v1  =  _v1;
		cost=_cost;
	}
}heap[10000];
int size;
void swap(int a,int b){
	node tmp = heap[a];
	heap[a] = heap[b];
	heap[b] = tmp;
}

void add(int a,double w){
	node tmp(a,w);
	heap[size] = tmp;
	int v = size++;
	while(v&&heap[v].cost<heap[father(v)].cost){
		swap(v,father(v));
		v = father(v);
	}
}
void del(){
	heap[0] = heap[--size];
	int v = 0;
	while(lchild(v)<size){
		if(rchild(v)==size){//右子出界 
			if(heap[v].cost>heap[lchild(v)].cost)swap(v,lchild(v));
			break;
		}
		else{
			if(heap[lchild(v)].cost>=heap[v].cost&&heap[rchild(v)].cost>=heap[v].cost)break;//左右子均满足堆序性 
			else if(heap[lchild(v)].cost<heap[v].cost&&heap[rchild(v)].cost>=heap[v].cost){//仅左子不满足堆序性 
				swap(v,lchild(v));
				v=lchild(v);
			}else if(heap[lchild(v)].cost>=heap[v].cost&&heap[rchild(v)].cost<heap[v].cost){
				swap(v,rchild(v));
				v=rchild(v);
			}else{
				if(heap[lchild(v)].cost<heap[rchild(v)].cost){
					swap(v,lchild(v));
					v=lchild(v);
				}else{
					swap(v,rchild(v));
					v=rchild(v);
				}
			}
		}
	}
}
void djs(){
	for(int i = 1;i<=n;++i)ans[i] = double(1<<24);
	ans[s] = 0;
	visited[s] = true;
	int tmp=start[s];double tmp2;
	while(lst[tmp].next!=-1){
		add(lst[tmp].v,lst[tmp].cost);
		tmp = lst[tmp].next;
	}
	while(size){
		while(size&&visited[heap[0].v1])del();
		if(size==0)break;
		ans[heap[0].v1] = heap[0].cost;
		tmp = heap[0].v1;double tmp2 = ans[tmp];
		visited[tmp] = true;
		del();
		int tmp3 = start[tmp];
		while(lst[tmp3].next!=-1){
			add(lst[tmp3].v,tmp2+lst[tmp3].cost);
			tmp3=lst[tmp3].next;
		}
	}
}
double dist(int a,int b){
	return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
} 
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);
	int va,vb;double tmpd;
	lst[0].next=-1;
	for(int i = 0;i<m;++i){
		scanf("%d %d",&va,&vb);
		tmpd = dist(va,vb);
		e_add(va,vb,tmpd);
		e_add(vb,va,tmpd);
	}
	scanf("%d %d",&s,&t);
	djs();
	printf("%.2lf",ans[t]);
	fclose(stdin);fclose(stdout);
	return 0;
}