题目描述
又到暑假了,住在城市 A 的 Car 想和朋友一起去城市旅游。
她知道每个城市都有 4 个飞机场,分别位于一个矩形的 4 个顶点上,同一个城市中两个机场之间有一条笔直的高速铁路,第 i个城市中高速铁路了的单位里程价格为 Ti,任意两个不同城市的机场之间均有航线,所有航线单位里程的价格均为 t。
注意:图中并没有标出所有的铁路与航线。
那么 Car 应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题,于是她来向你请教。
找出一条从城市 A 到 B 的旅游路线,出发和到达城市中的机场可以任意选取,要求总的花费最少。
第一眼看到这个题:太水了,大概就是把每两个车站之间建个边,spfa跑4次就可以了
于是快乐的zhn写出了下面这份快乐的代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#define int long long
using namespace std;
int n,T,A,B;
int s;
double dis[100004];
bool vis[100005];
struct NODE{
int x1,x2,x3,x4,y1,y2,y3,y4;//位置坐标
int t;//地铁钱
}zhn[105];
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*10+ch-'0';ch=getchar();}
return x*f;
}
inline double cal(int qzp,int cyk){
//pp和cs代表两个编号
int gt=qzp%4;
int gc=cyk%4;//用gt与gc来推出pp和cs分属于哪个城市,且gt与gc分别代表pp和cs为第几个站点
int gl=4-gt;//狗家三兄弟(不是
int sf=4-gc;//一行颓颓怪
int tf=(qzp+gl)/4;//丰丰田表示pp在哪个城市
int lzh=(cyk+sf)/4; //这行表示sf与lzh搞基
if(tf==lzh){
//pp和cs在一个窝里
if(gt==1&&gc==2){
return sqrt((zhn[tf].x1-zhn[tf].x2)*(zhn[tf].x1-zhn[tf].x2)+(zhn[tf].y1-zhn[tf].y2)*(zhn[tf].y1-zhn[tf].y2))*zhn[tf].t;
}
else if(gt==1&&gc==3){
return sqrt((zhn[tf].x1-zhn[tf].x3)*(zhn[tf].x1-zhn[tf].x3)+(zhn[tf].y1-zhn[tf].y3)*(zhn[tf].y1-zhn[tf].y3))*zhn[tf].t;
}
else if(gt==1&&gc==4){
return sqrt((zhn[tf].x1-zhn[tf].x4)*(zhn[tf].x1-zhn[tf].x4)+(zhn[tf].y1-zhn[tf].y4)*(zhn[tf].y1-zhn[tf].y4))*zhn[tf].t;
}
//
else if(gt==2&&gc==1){
return sqrt((zhn[tf].x2-zhn[tf].x1)*(zhn[tf].x2-zhn[tf].x1)+(zhn[tf].y2-zhn[tf].y1)*(zhn[tf].y2-zhn[tf].y1))*zhn[tf].t;
}
else if(gt==2&&gc==3){
return sqrt((zhn[tf].x2-zhn[tf].x3)*(zhn[tf].x2-zhn[tf].x3)+(zhn[tf].y2-zhn[tf].y3)*(zhn[tf].y2-zhn[tf].y3))*zhn[tf].t;
}
else if(gt==2&&gc==4){
return sqrt((zhn[tf].x2-zhn[tf].x4)*(zhn[tf].x2-zhn[tf].x4)+(zhn[tf].y2-zhn[tf].y4)*(zhn[tf].y2-zhn[tf].y4))*zhn[tf].t;
}
/
else if(gt==3&&gc==4){
return sqrt((zhn[tf].x3-zhn[tf].x4)*(zhn[tf].x3-zhn[tf].x4)+(zhn[tf].y3-zhn[tf].y4)*(zhn[tf].y3-zhn[tf].y4))*zhn[tf].t;
}
else if(gt==3&&gc==2){
return sqrt((zhn[tf].x3-zhn[tf].x2)*(zhn[tf].x3-zhn[tf].x2)+(zhn[tf].y3-zhn[tf].y2)*(zhn[tf].y3-zhn[tf].y2))*zhn[tf].t;
}
else if(gt==3&&gc==1){
return sqrt((zhn[tf].x3-zhn[tf].x1)*(zhn[tf].x3-zhn[tf].x1)+(zhn[tf].y3-zhn[tf].y1)*(zhn[tf].y3-zhn[tf].y1))*zhn[tf].t;
}
}
else if(tf!=lzh){
//cs与pp不在一个窝里
if(gt==1&&gc==2){
return sqrt((zhn[tf].x1-zhn[lzh].x2)*(zhn[tf].x1-zhn[lzh].x2)+(zhn[tf].y1-zhn[lzh].y2)*(zhn[tf].y1-zhn[lzh].y2))*T;
}
else if(gt==1&&gc==1){
return sqrt((zhn[tf].x1-zhn[lzh].x1)*(zhn[tf].x1-zhn[lzh].x1)+(zhn[tf].y1-zhn[lzh].y1)*(zhn[tf].y1-zhn[lzh].y1))*T;
}
else if(gt==1&&gc==3){
return sqrt((zhn[tf].x1-zhn[lzh].x3)*(zhn[tf].x1-zhn[lzh].x3)+(zhn[tf].y1-zhn[lzh].y3)*(zhn[tf].y1-zhn[lzh].y3))*T;
}
else if(gt==1&&gc==4){
return sqrt((zhn[tf].x1-zhn[lzh].x4)*(zhn[tf].x1-zhn[lzh].x4)+(zhn[tf].y1-zhn[lzh].y4)*(zhn[tf].y1-zhn[lzh].y4))*T;
}
//
else if(gt==2&&gc==2){
return sqrt((zhn[tf].x2-zhn[lzh].x2)*(zhn[tf].x2-zhn[lzh].x2)+(zhn[tf].y2-zhn[lzh].y2)*(zhn[tf].y2-zhn[lzh].y2))*T;
}
else if(gt==2&&gc==1){
return sqrt((zhn[tf].x2-zhn[lzh].x1)*(zhn[tf].x2-zhn[lzh].x1)+(zhn[tf].y2-zhn[lzh].y1)*(zhn[tf].y2-zhn[lzh].y1))*T;
}
else if(gt==2&&gc==3){
return sqrt((zhn[tf].x2-zhn[lzh].x3)*(zhn[tf].x2-zhn[lzh].x3)+(zhn[tf].y2-zhn[lzh].y3)*(zhn[tf].y2-zhn[lzh].y3))*T;
}
else if(gt==2&&gc==4){
return sqrt((zhn[tf].x2-zhn[lzh].x4)*(zhn[tf].x2-zhn[lzh].x4)+(zhn[tf].y2-zhn[lzh].y4)*(zhn[tf].y2-zhn[lzh].y4))*T;
}
///
else if(gt==3&&gc==1){
return sqrt((zhn[tf].x3-zhn[lzh].x1)*(zhn[tf].x3-zhn[lzh].x1)+(zhn[tf].y3-zhn[lzh].y1)*(zhn[tf].y3-zhn[lzh].y1))*T;
}
else if(gt==3&&gc==2){
return sqrt((zhn[tf].x3-zhn[lzh].x2)*(zhn[tf].x3-zhn[lzh].x2)+(zhn[tf].y3-zhn[lzh].y2)*(zhn[tf].y3-zhn[lzh].y2))*T;
}
else if(gt==3&&gc==3){
return sqrt((zhn[tf].x3-zhn[lzh].x3)*(zhn[tf].x3-zhn[lzh].x3)+(zhn[tf].y3-zhn[lzh].y3)*(zhn[tf].y3-zhn[lzh].y3))*T;
}
else if(gt==3&&gc==4){
return sqrt((zhn[tf].x3-zhn[lzh].x3)*(zhn[tf].x3-zhn[lzh].x3)+(zhn[tf].y3-zhn[lzh].y3)*(zhn[tf].y3-zhn[lzh].y3))*T;
}
/
else if(gt==4&&gc==1){
return sqrt((zhn[tf].x4-zhn[lzh].x1)*(zhn[tf].x4-zhn[lzh].x1)+(zhn[tf].y4-zhn[lzh].y1)*(zhn[tf].y4-zhn[lzh].y1))*T;
}
else if(gt==4&&gc==2){
return sqrt((zhn[tf].x4-zhn[lzh].x2)*(zhn[tf].x4-zhn[lzh].x2)+(zhn[tf].y4-zhn[lzh].y2)*(zhn[tf].y4-zhn[lzh].y2))*T;
}
else if(gt==4&&gc==3){
return sqrt((zhn[tf].x4-zhn[lzh].x3)*(zhn[tf].x4-zhn[lzh].x3)+(zhn[tf].y4-zhn[lzh].y3)*(zhn[tf].y4-zhn[lzh].y3))*T;
}
else if(gt==4&&gc==4){
return sqrt((zhn[tf].x4-zhn[lzh].x4)*(zhn[tf].x4-zhn[lzh].x4)+(zhn[tf].y4-zhn[lzh].y4)*(zhn[tf].y4-zhn[lzh].y4))*T;
}
}
}
inline double spfa(int num){
queue<int>q;
q.push(num);
memset(vis,0,sizeof(vis));
for(int i=1;i<=4*s;i++) dis[i]=99999999.99999;
vis[num]=1;
dis[num]=0;
while(!q.empty()){
int dmf=q.front();
q.pop();
for(int i=1;i<=s*4;i++){
//一个城市四个点,建立一张s*4的图图
double lgr=cal(dmf,i);
if(dis[i]>dis[dmf]+lgr){
dis[i]=dis[dmf]+lgr;
if(!vis[i]){
vis[i]=1;
q.push(i);
}
}
}
vis[dmf]=0;
}
double minn=2147483647.00;
minn=min(minn,dis[B*4]);
minn=min(minn,dis[B*4-1]);
minn=min(minn,dis[B*4-2]);
minn=min(minn,dis[B*4-3]);
return minn;
}
main(){
n=read();
while(n--){
int x11,y11,x22,y22;
s=read();T=read();A=read();B=read();
for(int i=1;i<=s;i++){
zhn[i].x1=read();
zhn[i].y1=read();
zhn[i].x2=read();
zhn[i].y2=read();
zhn[i].x3=read();
zhn[i].y3=read();
zhn[i].t=read();
x11=zhn[i].x2-zhn[i].x1;
y11=zhn[i].y2-zhn[i].y1;
x22=zhn[i].x3-zhn[i].x1;
y22=zhn[i].y3-zhn[i].y1;
if(x11*x22+y11*y22==0){
//x1,x4对应
zhn[i].x4=zhn[i].x2+zhn[i].x3-zhn[i].x1;
zhn[i].y4=zhn[i].y2+zhn[i].y3-zhn[i].y1;
}
else{
x11=zhn[i].x1-zhn[i].x2;
y11=zhn[i].y1-zhn[i].y2;
x22=zhn[i].x3-zhn[i].x2;
y22=zhn[i].y3-zhn[i].y2;
if(x11*x22+y11*y22==0){
//x2,x4对应
zhn[i].x4=zhn[i].x1+zhn[i].x3-zhn[i].x2;
zhn[i].y4=zhn[i].y1+zhn[i].y3-zhn[i].y2;
}
else{
//x3,x4对应
zhn[i].x4=zhn[i].x1+zhn[i].x2-zhn[i].x3;
zhn[i].y4=zhn[i].y1+zhn[i].y2-zhn[i].y3;
}
}
}
double minn=spfa(A*4);
minn=min(minn,spfa(A*4-1));
minn=min(minn,spfa(A*4-2));
minn=min(minn,spfa(A*4-3));
printf("%.1lf\n",minn);
}
return 0;
}
我感jio思路莫得什么问题,但是本机和lg上测的就是不一样
我拿出我的周易
掐指一算:
pp和cs 八字不合!不能成亲!(不是
lzh和sf太肥了!
于是修改了一下下
然后过了
我太骚了哈哈哈哈哈哈哈哈哈
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#define int long long
using namespace std;
int n,T,A,B;
int s;
double dis[100004];
bool vis[100005];
struct nNODE{
int x1,x2,x3,x4,y1,y2,y3,y4;//位置坐标
int t;//地铁钱
}zhn[105];
struct NODE{
int x,y;
int city;
}qzp[505];
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*10+ch-'0';ch=getchar();}
return x*f;
}
inline double cal(int gl,int gc){
//看来崔叔和pp的组合不可行,那我试试狗林和狗潮
if(qzp[gl].city==qzp[gc].city){
//gl gc在一个狗窝里
int cc=qzp[gl].city;
return sqrt((qzp[gl].x-qzp[gc].x)*(qzp[gl].x-qzp[gc].x)+(qzp[gl].y-qzp[gc].y)*(qzp[gl].y-qzp[gc].y))*zhn[cc].t;
}
else {
//狗林和狗潮不在一个狗窝里
return sqrt((qzp[gl].x-qzp[gc].x)*(qzp[gl].x-qzp[gc].x)+(qzp[gl].y-qzp[gc].y)*(qzp[gl].y-qzp[gc].y))*T;
}
}
inline double spfa(int num){
queue<int>q;
q.push(num);
memset(vis,0,sizeof(vis));
for(int i=1;i<=4*s;i++) dis[i]=99999999.99999;
vis[num]=1;
dis[num]=0;
while(!q.empty()){
int dmf=q.front();
q.pop();
for(int i=1;i<=s*4;i++){
//一个城市四个点,建立一张s*4的图图
double lgr=cal(dmf,i);//求lgr和段段搞基的长度
if(dis[i]>dis[dmf]+lgr){
dis[i]=dis[dmf]+lgr;
if(!vis[i]){
vis[i]=1;
q.push(i);
}
}
}
vis[dmf]=0;
}
double minn=2147483647.00;
minn=min(minn,dis[B*4]);
minn=min(minn,dis[B*4-1]);
minn=min(minn,dis[B*4-2]);
minn=min(minn,dis[B*4-3]);
return minn;
}
main(){
n=read();
while(n--){
int x11,y11,x22,y22;
int tot=0;
s=read();T=read();A=read();B=read();
for(int i=1;i<=s;i++){
zhn[i].x1=read();
zhn[i].y1=read();
zhn[i].x2=read();
zhn[i].y2=read();
zhn[i].x3=read();
zhn[i].y3=read();
zhn[i].t=read();
x11=zhn[i].x2-zhn[i].x1;
y11=zhn[i].y2-zhn[i].y1;
x22=zhn[i].x3-zhn[i].x1;
y22=zhn[i].y3-zhn[i].y1;
if(x11*x22+y11*y22==0){
//x1,x4对应
zhn[i].x4=zhn[i].x2+zhn[i].x3-zhn[i].x1;
zhn[i].y4=zhn[i].y2+zhn[i].y3-zhn[i].y1;
}
else{
x11=zhn[i].x1-zhn[i].x2;
y11=zhn[i].y1-zhn[i].y2;
x22=zhn[i].x3-zhn[i].x2;
y22=zhn[i].y3-zhn[i].y2;
if(x11*x22+y11*y22==0){
//x2,x4对应
zhn[i].x4=zhn[i].x1+zhn[i].x3-zhn[i].x2;
zhn[i].y4=zhn[i].y1+zhn[i].y3-zhn[i].y2;
}
else{
//x3,x4对应
zhn[i].x4=zhn[i].x1+zhn[i].x2-zhn[i].x3;
zhn[i].y4=zhn[i].y1+zhn[i].y2-zhn[i].y3;
}
}
++tot;
qzp[tot].city=i;
qzp[tot].x=zhn[i].x1;
qzp[tot].y=zhn[i].y1;
++tot;
qzp[tot].city=i;
qzp[tot].x=zhn[i].x2;
qzp[tot].y=zhn[i].y2;
++tot;
qzp[tot].city=i;
qzp[tot].x=zhn[i].x3;
qzp[tot].y=zhn[i].y3;
++tot;
qzp[tot].city=i;
qzp[tot].x=zhn[i].x4;
qzp[tot].y=zhn[i].y4;
}
double minn=spfa(A*4);
minn=min(minn,spfa(A*4-1));
minn=min(minn,spfa(A*4-2));
minn=min(minn,spfa(A*4-3));
printf("%.1lf\n",minn);
}
return 0;
}
事实证明
还是gl和gc搞基比较合适
cs和Pp不搞基
sf和lzh搞基但是太肥了
这种变量名慎用
还是dmf安全
么么哒!