目录

题面

题目链接

题目描述

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

注意：图中并没有标出所有的铁路与航线。

那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。

找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。

输入输出格式

输入格式

第一行为一个正整数 $ n (0 \leq n \leq 10) $ ，表示有 $ n $ 组测试数据。

每组的第一行有4个正整数 $ s,t,A,B $

$ s (0<S \leq 100) $ 表示城市的个数， $ t $ 表示飞机单位里程的价格，A，B分别为城市A，B的序号，($ 1 \leq A,B \leq s $)。

接下来有 $ s $ 行，其中第 $ i $ 行均有7个正整数 $ xi_1,yi_1,xi_2,yi_2,xi_3,yi_3,Ti $ 这当中的 $ (xi_1,yi_1),(xi_2,yi_2),(xi_3,yi_3) $ 分别是第 $ i $ 个城市中任意3个机场的坐标， $ T_i $ 为第 $ i $ 个城市高速铁路单位里程的价格。

输出格式

共有 $ n $ 行，每行1个数据对应测试数据。 保留一位小数。

输入输出样例

输入样例

13 10 1 31 1 1 3 3 1 302 5 7 4 5 2 18 6 8 8 11 6 3

输出样例

47.5

说明

【时空限制】

1000ms,128MB

思路

首先看题，应该是个最短路题。只要把所有飞机场之间建边就可以了。但，还要处理这样一些问题

1.第四个点的位置。题中给了三个点的位置，那么就可以算出三边的长度，其中最长的那一条边一定是对角线，这样就可以计算第四个顶点的坐标了

2.建边的长度。如果两个飞机场是一个城市的，那么边的长度（费用）是这个城市高铁费用乘上实际长度；否则是飞机费乘实际长度

3.这道题可以从A的任意机场出发，到任意一个B的机场就终止。那么怎么变成单源最短路径呢？那么实际上可以将初始城市的四个点变成一个，也就是将他们之间的长度都变成0，再跑最短路就可以了

AC代码

#include
    
     const int maxn=105;using namespace std;int s,t,a,b;struct City{    int x[4],y[4];    int T;}C[maxn];int tot,to[maxn*maxn],nxt[maxn*maxn],head[maxn];double d[maxn*maxn],ans[maxn*4];bool vis[maxn*4];priority_queue< pair
     
       > q;void Get0(int p){    City &q=C[p];    double l1=sqrt(((q.x[1])-(q.x[2]))*((q.x[1])-(q.x[2]))+((q.y[1])-(q.y[2]))*((q.y[1])-(q.y[2])));    double l2=sqrt(((q.x[1])-(q.x[3]))*((q.x[1])-(q.x[3]))+((q.y[1])-(q.y[3]))*((q.y[1])-(q.y[3])));    double l3=sqrt(((q.x[2])-(q.x[3]))*((q.x[2])-(q.x[3]))+((q.y[2])-(q.y[3]))*((q.y[2])-(q.y[3])));    double maxl=max(l1,max(l2,l3));    if(maxl==l1) q.x[0]=q.x[1]+q.x[2]-q.x[3],q.y[0]=q.y[1]+q.y[2]-q.y[3];    if(maxl==l2) q.x[0]=q.x[1]+q.x[3]-q.x[2],q.y[0]=q.y[1]+q.y[3]-q.y[2];    if(maxl==l3) q.x[0]=q.x[2]+q.x[3]-q.x[1],q.y[0]=q.y[2]+q.y[3]-q.y[1];}void Add(int u,int v,double len){    to[++tot]=v;nxt[tot]=head[u];head[u]=tot;d[tot]=len;    to[++tot]=u;nxt[tot]=head[v];head[v]=tot;d[tot]=len;}void Dijkstra(){    for(int i=0;i<4*s;i++) ans[i]=99999999;    ans[4*a]=0;ans[4*a+1]=0;ans[4*a+2]=0;ans[4*a+3]=0;    memset(vis,0,sizeof(vis));    q.push(make_pair(0,4*a));    q.push(make_pair(0,4*a+1));    q.push(make_pair(0,4*a+2));    q.push(make_pair(0,4*a+3));    while(!q.empty())    {        int u=q.top().second;q.pop();        if(vis[u]) continue;        vis[u]=true;        for(int i=head[u];i;i=nxt[i])        {            int v=to[i];            if(ans[u]+d[i]
     
    

总结

第四个点的处理算是一个小问题，还有将起点城市的四个点变成一个