洛谷1027 Car的旅行路线

卧槽竟然一遍就A了，可把身为蒟蒻的我nb坏了

刚开始让我做这道题，我是拒绝的，然后看完题发现，这就是道裸的最短路，连边搞就是了。

然后发现它只给三个点，看了题解才知道第四个点可以用向量点乘判断垂直来求，路燕我对不起你。

思路就是把一个城市分成四个点，同一个城市坐车，不同城市坐飞机，得到所有点的坐标和所在城市以后跑一遍最短路就行了。因为我很菜只会dijkstra，所以我就写的dijkstra。

#define pr pair<double,int>
#define mp make_pair

int t,n,p_pri,A,B,c_pri[405];
struct point{
    int x,y,city;
} pt[405];
double dis[405];
bool vis[405];

inline double get_dis(int x1,int y1,int x2,int y2) //两点间距离
{
    return (sqrt(1.0*(x1-x2)*(x1-x2)+1.0*(y1-y2)*(y1-y2)));
}

inline void get_pt(int x1,int y1,int x2,int y2,int x3,int y3,int id) //向量点乘判断垂直得到第四个点坐标
{
    pair<int,int> vector1=mp(x2-x1,y2-y1),vector2=mp(x3-x2,y3-y2),vector3=mp(x3-x1,y3-y1);
    if (vector1.first*vector2.first+vector1.second*vector2.second==0) pt[id].x=x1+x3-x2,pt[id].y=y1+y3-y2;
    else if (vector2.first*vector3.first+vector2.second*vector3.second==0) pt[id].x=x1+x2-x3,pt[id].y=y1+y2-y3;
    else pt[id].x=x2+x3-x1,pt[id].y=y2+y3-y1;
}

inline void dijkstra()
{
    priority_queue <pr,vector<pr>,greater<pr> > q;
    for (int i=1;i<=n*4;i++) dis[i]=1e9;
    memset(vis,0,sizeof(vis));
    for (int i=A*4-3;i<=A*4;i++)
    {
        dis[i]=0;
        q.push(mp(0,i));
    }
    while (!q.empty())
    {
        int x=q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x]=1;
        for (int i=1;i<=n*4;i++)
        {
            if (i==x) continue;
            double now=get_dis(pt[i].x,pt[i].y,pt[x].x,pt[x].y);
            if (pt[i].city==pt[x].city) now*=c_pri[pt[i].city];
            else now*=p_pri;
            if (dis[x]+now<dis[i])
            {
                dis[i]=dis[x]+now;
                q.push(mp(dis[i],i));
            }
        }
    }
}

int main()
{
    t=read();
    while (t--)
    {
        n=read(); p_pri=read(); A=read(); B=read();
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=3;j++)
            {
                pt[i*4-4+j].x=read();
                pt[i*4-4+j].y=read();
                pt[i*4-4+j].city=i;
            }
            get_pt(pt[i*4-3].x,pt[i*4-3].y,pt[i*4-2].x,pt[i*4-2].y,pt[i*4-1].x,pt[i*4-1].y,i*4);
            pt[i*4].city=i;
            c_pri[i]=read();
        }
        dijkstra();
        double ans=1e9;
        for (int i=B*4-3;i<=B*4;i++) ans=min(ans,dis[i]);
        printf("%.1f\n",ans);
    }
    return 0;
}