luogu1027 Car的旅行路线

luogu1027 Car的旅行路线

​​ 题目描述 又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。

图例（从上而下） 机场 高速铁路 飞机航线 注意：图中并没有 标出所有的铁路与航线。 那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。 找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。 输入输出格式 输入格式：

第一行为一个正整数n(0<=n<=10)，表示有n组测试数据。 每组的第一行有四个正整数s，t，A，B。 S(0

#include#include#include#include#include#define N 500using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}struct node{ int y,next;double z;}data[N*N*2];int h[N],num,TT,s,a,b,t,x[N][4],y[N][4],T[N];bool flag[N];double f[N];inline int calc(int x,int y){ x--;return x*4+y;}inline double calc1(int i,int j,int z){ return sqrt((x[i][j]-x[i][z])*(x[i][j]-x[i][z])+(y[i][j]-y[i][z])*(y[i][j]-y[i][z]));}inline double calc2(int i,int k,int j,int z){ return sqrt((x[i][k]-x[j][z])*(x[i][k]-x[j][z])+(y[i][k]-y[j][z])*(y[i][k]-y[j][z]));}inline void insert1(int x,int y,double z){ data[++num].y=y;data[num].next=h[x];h[x]=num;data[num].z=z; data[++num].y=x;data[num].next=h[y];h[y]=num;data[num].z=z;}void spfa(){ memset(f,0x48,sizeof(f));memset(flag,0,sizeof(flag));flag[calc(a,1)]=1;flag[calc(a,2)]=1;flag[calc(a,3)]=1;flag[calc(a,4)]=1; f[calc(a,1)]=0;f[calc(a,2)]=0;f[calc(a,3)]=0;f[calc(a,4)]=0;queue q;q.push(calc(a,4));q.push(calc(a,3));q.push(calc(a,2));q.push(calc(a,1)); while(!q.empty()){ int x=q.front();q.pop();flag[x]=0; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;double z=data[i].z; if (f[x]+zmx) mx=(x[i][j]-x[i][z])*(x[i][j]-x[i][z])+(y[i][j]-y[i][z])*(y[i][j]-y[i][z]),id1=j,id2=z; } } for (int j=1;j<=3;++j) if (j!=id1&&j!=id2) id3=j;int id4=4; x[i][4]=x[i][id1]+x[i][id2]-x[i][id3];y[i][4]=y[i][id1]+y[i][id2]-y[i][id3]; insert1(calc(i,id1),calc(i,id2),calc1(i,id1,id2)*T[i]); insert1(calc(i,id1),calc(i,id3),calc1(i,id1,id3)*T[i]); insert1(calc(i,id1),calc(i,id4),calc1(i,id1,id4)*T[i]); insert1(calc(i,id2),calc(i,id3),calc1(i,id2,id3)*T[i]); insert1(calc(i,id2),calc(i,id4),calc1(i,id2,id4)*T[i]); insert1(calc(i,id3),calc(i,id4),calc1(i,id3,id4)*T[i]); } for (int i=1;i<=s;++i){ for (int j=i+1;j<=s;++j){ for (int k=1;k<=4;++k){ for (int z=1;z<=4;++z){ insert1(calc(i,k),calc(j,z),calc2(i,k,j,z)*t); } } } } spfa();double ans=1e10; for (int i=1;i<=4;++i){ ans=min(ans,f[calc(b,i)]); }printf("%.1f",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。