玄学题目:洛谷P1027 Car的旅行路线 (写代码就是为了快乐.jpg!

题目描述
又到暑假了,住在城市 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安全
么么哒!

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-23 19:49
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-06 13:45
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议