題目描述

又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每個城市都有四個飛機場，分別位于一個矩形的四個頂點上，同一個城市中兩個機場之間有一條筆直的高速鐵路，第I個城市中高速鐵路了的單位里程價格為Ti，任意兩個不同城市的機場之間均有航線，所有航線單位里程的價格均為t。

圖例（從上而下）

機場 高速鐵路

飛機航線

　 注意：圖中并沒有

標(biāo)出所有的鐵路與航線。

那么Car應(yīng)如何安排到城市B的路線才能盡可能的節(jié)省花費呢?她發(fā)現(xiàn)這并不是一個簡單的問題，于是她來向你請教。

找出一條從城市A到B的旅游路線，出發(fā)和到達城市中的機場可以任意選取，要求總的花費最少。

輸入輸出格式

輸入格式：

?

第一行為一個正整數(shù)n(0<=n<=10)，表示有n組測試數(shù)據(jù)。

每組的第一行有四個正整數(shù)s，t，A，B。

S(0<S<=100)表示城市的個數(shù)，t表示飛機單位里程的價格，A，B分別為城市A，B的序號，(1<=A，B<=S)。

接下來有S行，其中第I行均有7個正整數(shù)xi1，yi1，xi2，yi2，xi3，yi3，Ti，這當(dāng)中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分別是第I個城市中任意三個機場的坐標(biāo)，T I為第I個城市高速鐵路單位里程的價格。

?

輸出格式：

?

共有n行，每行一個數(shù)據(jù)對應(yīng)測試數(shù)據(jù)。 保留一位小數(shù)

?

輸入輸出樣例

輸入樣例#1：
1 3 10 1 3 1 1 1 3 3 1 30 2 5 7 4 5 2 1 8 6 8 8 11 6 3 輸出樣例#1：
47.5
qvkongbu: #include <algorithm> #include <cstring> #include <cstdio> #include <cmath>#define y1 mmpusing namespace std;const int M(2333); const int N(110<<2); const double INF(1e15);int n,city_num,A,B; double dis[N][N],ans; int air_cost,road_cost[N]; int x1,x2,x3,x4,y1,y2,y3,y4,d1,d2,d3;struct Node {int x,y;Node(int x=0,int y=0): x(x),y(y) {} }airport[M];int Get_dis(int a,int aa,int b,int bb) {return (a-b)*(a-b)+(aa-bb)*(aa-bb); }void init() {memset(dis,0,sizeof(dis));memset(airport,0,sizeof(airport)); memset(road_cost,0,sizeof(road_cost)); }int main() {scanf("%d",&n);for(;n;n--){init();scanf("%d%d%d%d",&city_num,&air_cost,&A,&B);for(int i=1;i<=city_num;i++){scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);scanf("%d",road_cost+i);d1=Get_dis(x1,y1,x2,y2);d2=Get_dis(x2,y2,x3,y3);d3=Get_dis(x3,y3,x1,y1);if(d1>d2&&d1>d3)x4=x1+x2-x3,y4=y1+y2-y3;else if(d2>d1&&d2>d3)x4=x2+x3-x1,y4=y2+y3-y1;else if(d3>d1&&d3>d2)x4=x3+x1-x2,y4=y3+y1-y2;airport[(i<<2)-3]=Node(x1,y1);airport[(i<<2)-2]=Node(x2,y2);airport[(i<<2)-1]=Node(x3,y3);airport[(i<<2)-0]=Node(x4,y4);}for(int i=0;i<=(city_num<<2);i++)for(int j=0;j<=(city_num<<2);j++)if(i!=j) dis[i][j]=INF;for(int i=0;i<=(city_num<<2);i++)for(int j=0;j<=(city_num<<2);j++){double dist=sqrt(Get_dis(airport[i].x,airport[i].y,airport[j].x,airport[j].y));if(i+3>>2==j+3>>2)dis[i][j]=dist*(road_cost[i+3>>2]);elsedis[i][j]=dist*air_cost;}dis[0][(A<<2)-3]=0;dis[0][(A<<2)-2]=0;dis[0][(A<<2)-1]=0;dis[0][(A<<2)-0]=0;for(int k=0;k<=(city_num<<2);k++)for(int i=0;i<=(city_num<<2);i++)for(int j=0;j<=(city_num<<2);j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);ans=min(min(dis[0][(B<<2)-3],dis[0][(B<<2)-2]),min(dis[0][(B<<2)-1],dis[0][B<<2]));printf("%.1lf\n",ans);}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/lyqlyq/p/7216868.html

總結(jié)

以上是生活随笔為你收集整理的luogu P1027 Car的旅行路线的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。