(以“分类:最短路 ==摘要== {{信息题|Car的旅行路线 |http://www.codevs.cn/problem/1041/|1|100|题目读错|60|time=2015-8-2 18:30:09}} ==题解== *最短...”为内容创建页面) |
小 (难度) |
||
第1行: | 第1行: | ||
[[分类:最短路]] | [[分类:最短路]] | ||
==摘要== | ==摘要== | ||
− | {{信息题|Car的旅行路线 |http://www.codevs.cn/problem/1041/| | + | {{信息题|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]])。 |
题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因(初次提交分数) |
---|---|---|---|---|---|
Car的旅行路线 | ★★☆☆☆ | 答案正确 | 100 | 2015-8-2 18:30:09 | 题目读错(60) |
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);} };
#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(); 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口亨// 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); } }