查看CodeVS/1041的源代码 ←CodeVS/1041

[[分类:最短路]]
==摘要==
{{信息题|Car的旅行路线 |http://www.codevs.cn/problem/1041/|2|100|题目读错|60|time=2015-8-2 18:30:09}}

==题解==
*最短路仍然可以SPFA完成(同[[CodeVS/1077]][[CodeVS/1079]])，其他主要难点在于用简单的计算几何建边；
*首先先准备好简单的向量模板：
<pre>
struct v2{
    //点数据//
    double x,y;
    //构造函数//
    v2():x(0),y(0){};
    v2(double rx,double ry):x(rx),y(ry){};
    //线性运算//
    friend v2 operator -(v2 a,v2 b){return v2(a.x-b.x,a.y-b.y);}
    friend v2 operator +(v2 a,v2 b){return v2(a.x+b.x,a.y+b.y);}
    friend v2 operator *(v2 a,double t){return v2(a.x*t,a.y*t);}
    //点集//
    friend double operator *(v2 a,v2 b){return a.x*b.x+a.y*b.y;}
    //输入//
    void s(){scanf("%lf%lf",&x,&y);}
};
</pre>
*通过三个点<m>A(x_{i1},y_{i1}),B(x_{i2},y_{i2}),C(x_{i3},y_{i3})</m>，得到第四个点：
**通过判断点积<m>\vec{AB}</m><m>\dot</m><m>\vec{BC}=0</m>将直角顶点swap到B点；
**容易知道中点<m>M=\frac{A+C}{2}</m>
**从而推算出第四个点<m>D=M+\vec{BM}=A+C-B</m>；
*将这些点加入图，注意区分好城际和城内的不同。
==代码==
<pre>#include<cstdio>
#include<algorithm>
#include<iostream>
#include<set>
#include<queue>
#include<cstring>
#include<climits>
#include<cmath>
using  namespace std;
#define lld long long
queue<int> p;
vector< pair<int,double> > L[1024]={};
double Dis[1024][1024]={};
double rx[1024],ry[1024]={};
#define foreach(i,a) for(typeof(a.begin()) i=a.begin();i!=a.end();++i)
//距离计算//
double dis(int i,int j)
{
    return sqrt((rx[i]-rx[j])*(rx[i]-rx[j])+(ry[i]-ry[j])*(ry[i]-ry[j]));
}
//向量模板//
struct v2{
    double x,y;
    v2():x(0),y(0){};
    v2(double rx,double ry):x(rx),y(ry){};
    friend v2 operator -(v2 a,v2 b){return v2(a.x-b.x,a.y-b.y);}
    friend v2 operator +(v2 a,v2 b){return v2(a.x+b.x,a.y+b.y);}
    friend v2 operator *(v2 a,double t){return v2(a.x*t,a.y*t);}
    friend double operator *(v2 a,v2 b){return a.x*b.x+a.y*b.y;}
    void s(){scanf("%lf%lf",&x,&y);}
};
//读入四个点//
void scan(v2 xx[4])
{
    #define eps 1e-3
    v2 x,y,z;
    x.s();y.s();z.s();
    //通过点积找到直角顶点，记作y//
    if(abs((x-z)*(y-z))<=eps)swap(y,z);
    else if(abs((x-z)*(y-x))<=eps)swap(x,y);
    xx[0]=x,xx[1]=y,xx[2]=z;
    //算出第四个点//
    v2 mid=(x+z)*0.5;
    xx[3]=mid+mid-y;
}
int main(){
    int n,T,t,a,b;
    scanf("%d",&T);
    for(int tt=1;tt<=T;++tt)
    {
        scanf("%d%d%d%d",&n,&t,&a,&b);
        int Ans=INT_MAX;int Ansc;
        //建立城内边//
        for(int i=1;i<=4*n;i+=4)
        {
            double tt;
            v2 xx[4]={};//修正：0 to 3的数组要开4
            scan(xx);
            for(int r=0;r<=3;++r)
                rx[i+r]=xx[r].x,ry[i+r]=xx[r].y;
            scanf("%lf",&tt);
            for(int j=0;j<=3;++j)
                for(int r=0;r<=3;++r)//修正：题目描述对角线也有连边
                L[i+j].push_back( make_pair(r+i,tt*dis(i+j,r+i)) );
        }
        //建立城际边//
        for(int i=1;i<=4*n;++i)
        {
            for(int j=1;j<=4*n;++j)
            {
                //新建路径//
                L[i].push_back( make_pair(j,t*dis(i,j)) );
                L[j].push_back( make_pair(i,t*dis(i,j)) );
                Dis[i][j]=1e+30;
            }
        }
        //伦家就是喜欢SPFA口亨,SPFA主程序(Floyd或者其他最短路也Acceptable，数据量不大)//
        for(int r=1+4*(a-1);r<=4+4*(a-1);++r)
        {
            p.push(r);Dis[r][r]=0;
            while(!p.empty())//队列非空//
            {
                foreach(i,L[p.front()])//遍历//
                    if(Dis[r][p.front()]+i->second<Dis[r][i->first])//判断Dis是否更优//
                    {
                        Dis[r][i->first]=Dis[r][p.front()]+i->second;//更新目标点并入队//
                        p.push(i->first);
                        if(isupper(i->first))//统计Ans//
                            if(Dis[r][i->first]<Ans)
                            {
                                Ans=Dis[r][i->first];
                                Ansc=i->first;
                            }
                    }
                p.pop();
            }

        }
        //统计答案//
        double ans=1e+30;
        for(int i=1;i<=4;++i)
            for(int j=1;j<=4;++j)
                ans=min(Dis[(a-1)*4+i][(b-1)*4+j],ans);
        printf("%.1lf\n",ans);
    }
}
</pre>