AC日记——Car的旅行路线 洛谷 P1027

Car的旅行路线

思路：

　　这题不难，就是有点恶心；

　　而且，请认真读题目（就是题目卡死劳资）；

来，上代码：

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 807

#define maxm 860005

#define INF 0x7fffffff

struct CityType {

    double x[],y[],c;

};

struct CityType city[maxn];

int T,n,s,t,head[maxn],E[maxm],V[maxm];

int cnt,que[maxn<<];

double W[maxm],dis[maxn],c;

bool if_[maxn];

inline double d(int now,int v1,int v2)

{

    double x1=city[now].x[v1],x2=city[now].x[v2];

    double y1=city[now].y[v1],y2=city[now].y[v2];

    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);

}

inline void edge_add(int u,int v,double w)

{

    E[++cnt]=head[u],V[cnt]=v,W[cnt]=w,head[u]=cnt;

    E[++cnt]=head[v],V[cnt]=u,W[cnt]=w,head[v]=cnt;

}

double ds(int u,int v1,int v,int v2)

{

    double xx=city[u].x[v1]-city[v].x[v2];

    double yy=city[u].y[v1]-city[v].y[v2];

    return sqrt(xx*xx+yy*yy);

}

void spfa()

{

    memset(if_,false,sizeof(if_));

    memset(dis,0x7f,sizeof(dis));

    int h=,tail=;que[]=s*-,que[]=s*-;

    que[]=s*-,que[]=s*,if_[s*-]=true;

    if_[s*-]=true,if_[s*-]=true,if_[s*]=true;

    dis[s*-]=,dis[s*-]=,dis[s*-]=,dis[s*]=;

    while(h<tail)

    {

        int now=que[h++];if_[now]=false;

        for(int i=head[now];i;i=E[i])

        {

            if(dis[V[i]]>dis[now]+W[i])

            {

                dis[V[i]]=dis[now]+W[i];

                if(!if_[V[i]]) if_[V[i]]=true,que[tail++]=V[i];

            }

        }

    }

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        memset(head,,sizeof(head)),cnt=;

        scanf("%d%lf%d%d",&n,&c,&s,&t);

        for(int i=;i<=n;i++)

        {

            for(int v=;v<;v++) scanf("%lf%lf",&city[i].x[v],&city[i].y[v]);

            scanf("%lf",&city[i].c);

            double d01=d(i,,),d02=d(i,,),d12=d(i,,);

            int pos=i*-;

            if(d01+d02==d12)

            {

                city[i].x[]=city[i].x[]+city[i].x[]-city[i].x[];

                city[i].y[]=city[i].y[]+city[i].y[]-city[i].y[];

            }

            else if(d01+d12==d02)

            {

                city[i].x[]=city[i].x[]+city[i].x[]-city[i].x[];

                city[i].y[]=city[i].y[]+city[i].y[]-city[i].y[];

            }

            else

            {

                city[i].x[]=city[i].x[]+city[i].x[]-city[i].x[];

                city[i].y[]=city[i].y[]+city[i].y[]-city[i].y[];

            }

            for(int j=;j<=;j++)

            {

                for(int v=j+;v<=;v++) edge_add(pos+j,pos+v,sqrt(d(i,j,v))*city[i].c);

            }

        }

        for(int i=;i<=n;i++)

        {

            for(int j=i+;j<=n;j++)

            {

                int posi=i*-,posj=j*-;

                for(int v=;v<;v++)

                {

                    for(int z=;z<;z++) edge_add(v+posi,z+posj,ds(i,v,j,z)*c);

                }

            }

        }

        spfa();double ans=INF;

        for(int i=;i<=;i++) ans=min(ans,dis[i+t*-]);

        printf("%.1lf",ans);

    }

    return ;

}