记录编号	500200	评测结果	WWAAWAAWWW
题目名称	高速公路	最终得分	40
用户昵称	雨季	是否通过	未通过
代码语言	C++	运行时间	0.003 s
提交时间	2018-07-09 21:01:20	内存使用	15.70 MiB

#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
#define N 10005
#define mp make_pair

int n;
int cnt;
int S,T;
map< pair<int,int>,int > way;

struct node {
	int v,nex;
	double c;
}e[1000005];
int tot,h[N];
void add(int u,int v,double c) {
	e[++tot].v=v,e[tot].c=c,e[tot].nex=h[u],h[u]=tot;
	e[++tot].v=u,e[tot].c=c,e[tot].nex=h[v],h[v]=tot;
}
double getl(int a,int b,int c,int d) {
	return sqrt(1.0*(a-c)*(a-c)+1.0*(b-d)*(b-d));
}

bool vis[N];
double dis[N];
queue<int>q;
void spfa() {
	for(int i=1;i<=cnt;++i) dis[i]=1e9;
	q.push(S);
	dis[S]=0;
	int x,xx;
	while(!q.empty()) {
		x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=h[x];i;i=e[i].nex) {
			xx=e[i].v;
			if(dis[xx]>dis[x]+e[i].c) {
				dis[xx]=dis[x]+e[i].c;
				if(!vis[xx]) {
					vis[xx]=1;
					q.push(xx);
				}
			}
		}
	}
}

int main()
{
	freopen("highway.in","r",stdin);
	freopen("highway.out","w",stdout);
	scanf("%d",&n);
	int a,b,c,d;
	for(int i=1;i<=n;++i) {
		scanf("%d%d%d%d",&a,&b,&c,&d);
		if(!way[mp(a,b)]) way[mp(a,b)]=++cnt;
		if(!way[mp(c,d)]) way[mp(c,d)]=++cnt;
		add(way[mp(a,b)],way[mp(c,d)],getl(a,b,c,d));//cout<<getl(a,b,c,d)<<" "<<e[tot].c<<endl;
		if(i==1) S=way[mp(a,b)];
		if(i==n) T=way[mp(c,d)];
	}
	spfa();
	double V;
	scanf("%lf",&V);//;cout<<"eeeeeeeeeeee "<<dis[4]<<endl;
	printf("%.2lf\n",dis[T]/V);
	return 0;
}
/*

6
100 400 450 700
100 750 700 500
700 0 100 400
300 150 450 400
700 500 700 0
450 400 700 500
1
*/