```
#include<bits/stdc++.h>
#include<iomanip>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<ctime>
#include<bitset>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<map>
#include<stack>
#include<algorithm>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void put(int x)
{
if(x==0){putchar('0');putchar(' ');return;}
if(x<0)putchar('-'),x=-x;
int num=0;char ch[50];
while(x)ch[++num]=x%10+'0',x/=10;
while(num)putchar(ch[num--]);
putchar(' ');return;
}
priority_queue<pair<double,int> > q;
const int maxn=5000;
int lin[maxn<<1],ver[maxn<<1],nex[maxn<<1],len=0;
double e[maxn<<1];
double ans,v,u;
int n;
double s2,s1,e1,e2;
double d[maxn];
int vis[maxn],vis1[maxn];
int a[maxn][maxn];
struct wy
{
double x,y;
int id;
}t[maxn<<1];
double dis(double u1,double u2,double u3,double u4)
{
return sqrt((u1-u2)*(u1-u2)+(u3-u4)*(u3-u4));
}
void add(int x,int y,double z)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
e[len]=z;
}
void dij(int x)
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n+5;i++)d[i]=2147483626.111;
q.push(make_pair(0,x));
d[x]=0;
while(q.size()!=0)
{
int te=q.top().second;q.pop();
//if(te==n+2)return;
if(vis[te]==1)continue;
vis[te]=1;//cout<<te<<endl;
vis1[te]=1;
for(int i=lin[te];i;i=nex[i])
{
int tn=ver[i];
if(d[tn]>d[te]+e[i]&&vis1[tn]!=1)
{
d[tn]=d[te]+e[i];
q.push(make_pair(-d[tn],tn));
}
}
}
return;
}
int main()
{
//freopen("1.in","r",stdin);
scanf("%lf%lf",&v,&u);
n=read();
for(int i=1;i<=n;i++)
{
t[i].id=i;
scanf("%lf%lf",&t[i].x,&t[i].y);
}
while(1)
{
int x,y;
x=read();y=read();
if(x==0||y==0)break;
if(x==y)continue;
if(a[x][y]==1)continue;
if(a[y][x]==1)continue;
add(x,y,dis(t[x].x,t[y].x,t[x].y,t[y].y)*u);
add(y,x,dis(t[x].x,t[y].x,t[x].y,t[y].y)*u);
a[x][y]=1;a[y][x]=1;
}
scanf("%lf%lf%lf%lf",&s1,&e1,&s2,&e2);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(a[i][j]!=1&&a[j][i]!=1)
{
add(t[i].id,t[j].id,dis(t[i].x,t[j].x,t[i].y,t[j].y)*v);
add(t[j].id,t[i].id,dis(t[i].x,t[j].x,t[i].y,t[j].y)*v);
a[i][j]=1;a[j][i]=1;
}
}
}
for(int i=1;i<=n;i++)
{
add(n+1,t[i].id,dis(s1,t[i].x,e1,t[i].y)*v);
add(t[i].id,n+1,dis(s1,t[i].x,e1,t[i].y)*v);
add(n+2,t[i].id,dis(s2,t[i].x,e2,t[i].y)*v);
add(t[i].id,n+2,dis(s2,t[i].x,e2,t[i].y)*v);
}
add(n+1,n+2,dis(s1,s2,e1,e2)*v);
add(n+2,n+1,dis(s1,s2,e1,e2)*v);
//cout<<dis(s1,s2,e1,e2)<<endl;
//for(int i=lin[n+1];i;i=nex[i])cout<<e[i]<<endl;
dij(n+1);
printf("%.4lf",d[n+2]);
return 0;
}
```
by chdy @ 2018-12-18 20:27:02
写了对拍 和题解拍了一下几组数据超时,或者wa但是看不出来为什么哎
by chdy @ 2018-12-19 19:07:38
求数据或者dalao帮忙看看
by chdy @ 2018-12-19 19:08:53
一道黄题毁心情,难受qwq
by chdy @ 2018-12-19 19:33:17
https://www.luogu.org/recordnew/lists?uid=59688&pid=P1907
辣鸡题目 颓我精神
by chdy @ 2018-12-19 21:03:42