1827：【01NOIP提高组】Car的旅行路线

哇这些真题终于正经起来奥

刚看这道题很不自信觉得自己肯定不能建图成功甚至想过用贪心。。

后来一想发现建图还是蛮容易的，AI我是真的蠢

话说一本通真的很坑啊，把原题的保留1位改成了2

我把在洛谷AC的代码交上去查了好久才发现。。

（话说为什么把读入优化换成scanf效率快了一千倍。。）

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int n,s,t,A,B,T[maxn<<];

double dis[maxn<<];

bool book[maxn<<];

/*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<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}*/

struct data{

    int city;

    int x,y;

}a[maxn<<];

inline int power_2(int x)

{

    return x*x;

}

void getlast(int x1,int y1,int x2,int y2,int x3,int y3,int i)

{

    int x4,y4;

    int dis1=power_2(x1-x2)+power_2(y1-y2),

        dis2=power_2(x1-x3)+power_2(y1-y3),

        dis3=power_2(x2-x3)+power_2(y2-y3);

    if(dis2==dis1+dis3) x4=x3-x2+x1,y4=y3+y1-y2;

    if(dis1==dis2+dis3) x4=x2-x3+x1,y4=y2+y1-y3;

    if(dis3==dis1+dis2) x4=x3-x1+x2,y4=y3+y2-y1;

    a[i+].x=x4;a[i+].y=y4;

}//这道题目唯一需要注意的点大概就是这个求第四个点

inline double distance(int x1,int y1,int x2,int y2)

{

    return sqrt(power_2(x1-x2)+power_2(y1-y2));

}

void SPFA()

{

    memset(book,,sizeof(book));

    queue <int> q;

    for(int i=;i<=s<<;i++) dis[i]=;

    for(int i=A*-;i<=A*;i++) dis[i]=,q.push(i),book[i]=;

    while(!q.empty())

    {

        int u=q.front();q.pop();book[u]=;

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

        {

            if(i==u) continue;

            double cost=distance(a[i].x,a[i].y,a[u].x,a[u].y);

            if(a[i].city==a[u].city) cost*=T[a[i].city];

            else cost*=t;

            if(dis[i]>dis[u]+cost)

            {

                dis[i]=dis[u]+cost;

                if(!book[i])

                {

                    book[i]=;

                    q.push(i);

                }

            }

         }

    }

}

void init()

{

    //memset(t,0,sizeof(t));

    memset(a,,sizeof(a));

    scanf("%d%d%d%d",&s,&t,&A,&B);

    int i;

    for(i=;i<=s<<;i+=)

    {

        //int x1,x2,x3,y1,y2,y3;

        scanf("%d%d%d%d%d%d%d",&a[i].x,&a[i].y,&a[i+].x,&a[i+].y,&a[i+].x,&a[i+].y,&T[i/+]);

        a[i].city=a[i+].city=a[i+].city=a[i+].city=i/+;

        getlast(a[i].x,a[i].y,a[i+].x,a[i+].y,a[i+].x,a[i+].y,i);

    }

}

int main()

{

    scanf("%d",&n);

    int i;

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

    {

        init();

        SPFA();

        double ans=dis[B<<];

        for(int j=B*-;j<B*;j++) if(ans>dis[j]) ans=dis[j];

        printf("%.2lf\n",ans);

    }

    return ;

}