M_sea

洛谷1027 Car的旅行路线
洛谷分析这样的题显然可以建图搞。把机场全都连起来即可。这样就构成了一个完全图。既然是完全图,考虑Dijkstra。...
扫描右侧二维码阅读全文
04
2018/10

洛谷1027 Car的旅行路线

洛谷

分析

这样的题显然可以建图搞。

把机场全都连起来即可。这样就构成了一个完全图。

既然是完全图,考虑Dijkstra。

建两个虚点,一个向A的四个机场各连一条边权为0的无向边边,另一个同理,连到B上。

最后跑出来就行了。


现在的问题是,已知矩形三个点怎么求出第四个。

这三个点显然会构成一个直角三角形。

那么求直角边上的中点,再对过去就好了。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
#define sqr(x) ((x)*(x))
using namespace std;

struct Point { double x,y; int id; };
Point a[410];

struct Edge { int v,nxt; double w; };
Edge e[300010];
int head[410],cnt=0;

inline void addEdge(int u,int v,double w)
{
    e[++cnt].v=v; e[cnt].w=w;
    e[cnt].nxt=head[u]; head[u]=cnt;
    e[++cnt].v=u; e[cnt].w=w;
    e[cnt].nxt=head[v]; head[v]=cnt;
}

int n,m;
double t[410];
double Plane;
int A,B;

inline double dis(Point a,Point b)
{
    return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
inline Point GetPoint(Point a,Point b,Point c)
{
    double AB=dis(a,b),BC=dis(b,c),CA=dis(c,a);
    if (BC>AB&&BC>CA) swap(a,c);
    else if (CA>AB&&CA>BC) swap(b,c);
    Point Mid; Mid.x=(a.x+b.x)/2.0; Mid.y=(a.y+b.y)/2.0;
    Point d; d.x=Mid.x+(Mid.x-c.x); d.y=Mid.y+(Mid.y-c.y);
    d.id=a.id; return d;
}

inline void Build()
{
    for (re int i=0;i<n/4;i++)
    {
        int e=i*4+1,b=i*4+2,c=i*4+3,d=i*4+4,tmp=t[i+1];
        addEdge(e,b,dis(a[e],a[b])*tmp); addEdge(e,d,dis(a[e],a[d])*tmp);
        addEdge(e,c,dis(a[e],a[c])*tmp); addEdge(b,d,dis(a[b],a[d])*tmp);
        addEdge(b,c,dis(a[b],a[c])*tmp); addEdge(c,d,dis(a[c],a[d])*tmp);
    }
    for (re int i=1;i<=n;i++)
        for (re int j=i+1;j<=n;j++)
        {
            if (a[i].id!=a[j].id)
                addEdge(i,j,dis(a[i],a[j])*Plane);
        }
}

struct HeapNode
{
    int u; double d;
    HeapNode(int u_=0,double d_=0.0) { this->u=u_; this->d=d_; }
    bool operator <(const HeapNode& rhs) const
    {
        return d>rhs.d;
    }
};

double dist[410];

inline void Dijkstra(int s)
{
    priority_queue<HeapNode> Q;
    for (re int i=0;i<=n+1;i++) dist[i]=999999999.0;
    dist[s]=0; Q.push((HeapNode){s,0});
    while (!Q.empty())
    {
        HeapNode fr=Q.top(); Q.pop();
        int u=fr.u; double d=fr.d;
        if (dist[u]!=d) continue;
        for (re int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v; double w=e[i].w;
            if (d+w<dist[v])
            {
                dist[v]=d+w;
                Q.push((HeapNode){v,dist[v]});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int T; cin>>T;
    while (T--)
    {
        cnt=0; m=0; memset(head,0,sizeof(head));
        cin>>n>>Plane>>A>>B; int k=0;
        for (re int i=1;i<=n;i++)
        {
            k++; cin>>a[k].x>>a[k].y; a[k].id=i;
            k++; cin>>a[k].x>>a[k].y; a[k].id=i;
            k++; cin>>a[k].x>>a[k].y; a[k].id=i;
            k++; a[k]=GetPoint(a[k-3],a[k-2],a[k-1]);
            cin>>t[i];
        }
        if (n==1) { printf("0.0\n"); }
        else
        {
            n=k; Build();
            addEdge(0,A*4-3,0); addEdge(0,A*4-2,0);
            addEdge(0,A*4-1,0); addEdge(0,A*4,0);
            addEdge(n+1,B*4-3,0); addEdge(n+1,B*4-2,0);
            addEdge(n+1,B*4-1,0); addEdge(n+1,B*42,0);
            Dijkstra(0); printf("%.1f\n",floor(dist[n+1]*10+0.5)/10.0);
        }
    }
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 28 PM

发表评论