Car的旅行路线

题目描述

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

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

输入描述:

第一行为一个正整数n( 0 ≤ n ≤ 10 )，表示有n组测试数据。
每组的第一行有4个正整数S,t,A,B。
S( 0 < S ≤ 100 )表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，( 1 ≤ A，B ≤ S )。
接下来有S行，其中第i行均有7个正整数 xi1,yi1,xi2,yi2,xi3,yi3,Ti 这当中的(xi1,yi1)，(xi2,yi2)，(xi3,yi3)分别是第i个城市中任意3个机场的坐标，Ti 为第i个城市高速铁路单位里程的价格。

输出描述:

共有n行，每行1个数据对应测试数据（最小花费）。保留一位小数。

题解

对于本题数据范围着实很小。我们直接建一个图然后跑最短路就好了。
可能只有建图写着比较麻烦吧，应该算是一个最短路裸题。具体细节看代码注释吧

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
struct point{
    double x, y;
    int id;
}v[450];
vector<pair<int,double> > t[450];
double powdis(point a,point b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int T[105];
double dis[440];
int tot=0;
int s,tt,a,b;
double dij(){
    priority_queue<pair<double,int> >Q;
    for(int i=(a-1)*4+1;i<=a*4;++i){
        Q.push({0,i});
        dis[i]=0;
    }
    double ans=1e9;
    while(!Q.empty()){
        pair<double,int> now=Q.top();
        Q.pop();
        if(v[now.se].id==b){
            ans=min(ans,dis[now.se]);
        }
        for(auto k:t[now.se]){
            if(dis[k.fi]>dis[now.se]+k.se){
                dis[k.fi]=dis[now.se]+k.se;
                //cout<<"dis["<<k.fi<<"]="<<dis[k.fi]<<endl;
                Q.push({-dis[k.fi],k.fi});
            }
        }
    }
    return ans;
}
void solve(){
    s=gn(),tt=gn(),a=gn(),b=gn();
    repi(i,1,s){
        repi(j,1,3){
            ++tot;
            scanf("%lf%lf",&v[tot].x,&v[tot].y);
            v[tot].id=i;
        }
        scanf("%d",&T[i]);
        double ab=powdis(v[tot-2],v[tot-1]);
        double ac=powdis(v[tot-2],v[tot]);
        double bc=powdis(v[tot-1],v[tot]);
        if(ab+ac==bc){
            double x=v[tot-1].x+v[tot].x-v[tot-2].x;
            double y=v[tot-1].y+v[tot].y-v[tot-2].y;
            v[++tot]={x,y,i};
        }
        else if(ab+bc==ac){
            double x=v[tot-2].x+v[tot].x-v[tot-1].x;
            double y=v[tot-2].y+v[tot].y-v[tot-1].y;
            v[++tot]={x,y,i};
        }
        else {
            double x=v[tot-1].x+v[tot-2].x-v[tot].x;
            double y=v[tot-1].y+v[tot-2].y-v[tot].y;
            v[++tot]={x,y,i};
        }//求出第四个点
        repr(j,tot,tot-3){
            repi(k,tot-3,tot){
                if(j!=k)t[j].pb(MP(k,sqrt(powdis(v[j],v[k]))*T[i]));
            }
        }//把相同城市之间的高铁航道建好
    }
    for(int i=1;i<=tot;++i){
        dis[i]=1e9;
        for(int j=1;j<=tot;++j){
            if(v[i].id==v[j].id)continue;
            t[i].pb(MP(j,sqrt(powdis(v[i],v[j]))*tt));
        }
    }//把不同城市之间的飞机航道建好
    printf("%.1f\n",dij());//跑最短路
}
////////////////////////////////////////////////////////////////////////
int main(){
    int t;
    t=gn();
    while(t--)
        solve();
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/