(以“分类:最短路 ==摘要== {{信息题|Car的旅行路线 |http://www.codevs.cn/problem/1041/|1|100|题目读错|60|time=2015-8-2 18:30:09}} ==题解== *最短...”为内容创建页面)
 
(注释)
 
(未显示1个用户的1个中间版本)
第1行: 第1行:
 
[[分类:最短路]]
 
[[分类:最短路]]
 
==摘要==
 
==摘要==
{{信息题|Car的旅行路线 |http://www.codevs.cn/problem/1041/|1|100|题目读错|60|time=2015-8-2 18:30:09}}
+
{{信息题|Car的旅行路线 |http://www.codevs.cn/problem/1041/|2|100|题目读错|60|time=2015-8-2 18:30:09}}
 +
 
 
==题解==
 
==题解==
*最短路仍然可以SPFA完成(同[[CodeVS/1077]][[CodeVS/1079]])
+
*最短路仍然可以SPFA完成(同[[CodeVS/1077]][[CodeVS/1079]]),其他主要难点在于用简单的计算几何建边;
*其他的难度在于用简单的计算几何建边:
+
*首先先准备好简单的向量模板:
**首先先准备好简单的向量模板:
+
 
<pre>
 
<pre>
 
struct v2{
 
struct v2{
第23行: 第23行:
 
};
 
};
 
</pre>
 
</pre>
**通过三个点<m>A(x_{i1},y_{i1}),B(x_{i2},y_{i2}),C(x_{i3},y_{i3})</m>,得到第四个点:
+
*通过三个点<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>\vec{AB}</m><m>\dot</m><m>\vec{BC}=0</m>将直角顶点swap到B点;
***容易知道中点<m>M=\frac{A+C}{2}</m>
+
**容易知道中点<m>M=\frac{A+C}{2}</m>
***从而推算出第四个点<m>D=M+\vec{BM}=A+C-B</m>;
+
**从而推算出第四个点<m>D=M+\vec{BM}=A+C-B</m>;
 +
*将这些点加入图,注意区分好城际和城内的不同。
 
==代码==
 
==代码==
 
<pre>#include<cstdio>
 
<pre>#include<cstdio>
第43行: 第44行:
 
double rx[1024],ry[1024]={};
 
double rx[1024],ry[1024]={};
 
#define foreach(i,a) for(typeof(a.begin()) i=a.begin();i!=a.end();++i)
 
#define foreach(i,a) for(typeof(a.begin()) i=a.begin();i!=a.end();++i)
 +
//距离计算//
 
double dis(int i,int j)
 
double dis(int i,int j)
 
{
 
{
 
     return sqrt((rx[i]-rx[j])*(rx[i]-rx[j])+(ry[i]-ry[j])*(ry[i]-ry[j]));
 
     return sqrt((rx[i]-rx[j])*(rx[i]-rx[j])+(ry[i]-ry[j])*(ry[i]-ry[j]));
 
}
 
}
 +
//向量模板//
 
struct v2{
 
struct v2{
 
     double x,y;
 
     double x,y;
第57行: 第60行:
 
     void s(){scanf("%lf%lf",&x,&y);}
 
     void s(){scanf("%lf%lf",&x,&y);}
 
};
 
};
 +
//读入四个点//
 
void scan(v2 xx[4])
 
void scan(v2 xx[4])
 
{
 
{
第62行: 第66行:
 
     v2 x,y,z;
 
     v2 x,y,z;
 
     x.s();y.s();z.s();
 
     x.s();y.s();z.s();
 +
    //通过点积找到直角顶点,记作y//
 
     if(abs((x-z)*(y-z))<=eps)swap(y,z);
 
     if(abs((x-z)*(y-z))<=eps)swap(y,z);
 
     else if(abs((x-z)*(y-x))<=eps)swap(x,y);
 
     else if(abs((x-z)*(y-x))<=eps)swap(x,y);
 
     xx[0]=x,xx[1]=y,xx[2]=z;
 
     xx[0]=x,xx[1]=y,xx[2]=z;
 +
    //算出第四个点//
 
     v2 mid=(x+z)*0.5;
 
     v2 mid=(x+z)*0.5;
 
     xx[3]=mid+mid-y;
 
     xx[3]=mid+mid-y;
第75行: 第81行:
 
         scanf("%d%d%d%d",&n,&t,&a,&b);
 
         scanf("%d%d%d%d",&n,&t,&a,&b);
 
         int Ans=INT_MAX;int Ansc;
 
         int Ans=INT_MAX;int Ansc;
 +
        //建立城内边//
 
         for(int i=1;i<=4*n;i+=4)
 
         for(int i=1;i<=4*n;i+=4)
 
         {
 
         {
第87行: 第94行:
 
                 L[i+j].push_back( make_pair(r+i,tt*dis(i+j,r+i)) );
 
                 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 i=1;i<=4*n;++i)
 
         {
 
         {
第98行: 第105行:
 
             }
 
             }
 
         }
 
         }
         //伦家就是喜欢SPFA口亨//
+
         //伦家就是喜欢SPFA口亨,SPFA主程序(Floyd或者其他最短路也Acceptable,数据量不大)//
 
         for(int r=1+4*(a-1);r<=4+4*(a-1);++r)
 
         for(int r=1+4*(a-1);r<=4+4*(a-1);++r)
 
         {
 
         {
第120行: 第127行:
  
 
         }
 
         }
 
+
        //统计答案//
 
         double ans=1e+30;
 
         double ans=1e+30;
 
         for(int i=1;i<=4;++i)
 
         for(int i=1;i<=4;++i)
第128行: 第135行:
 
     }
 
     }
 
}
 
}
 
 
</pre>
 
</pre>

2015年8月2日 (日) 18:45的最后版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
Car的旅行路线 ★★☆☆☆ 答案正确 100 2015-8-2 18:30:09 题目读错(60)


题解

  • 最短路仍然可以SPFA完成(同CodeVS/1077CodeVS/1079),其他主要难点在于用简单的计算几何建边;
  • 首先先准备好简单的向量模板:
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);}
};
  • 通过三个点A(x_{i1},y_{i1}),B(x_{i2},y_{i2}),C(x_{i3},y_{i3}),得到第四个点:
    • 通过判断点积\vec{AB}\dot\vec{BC}=0将直角顶点swap到B点;
    • 容易知道中点M=\frac{A+C}{2}
    • 从而推算出第四个点D=M+\vec{BM}=A+C-B
  • 将这些点加入图,注意区分好城际和城内的不同。

代码

#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);
    }
}

著作权声明[编辑]

关于[编辑]