建图，最短路

题意：

分析：

没有什么难以思考的地方，关键就是建图，我们以每个机场为节点建图。成功建图后跑4次dijstra算法
取得城市a到城市b的最小路径就行了。
但是，在此题中建图这件事还真是挺大工程的。代码量巨大，烦死我了。

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<iomanip>
using namespace std;
const int max_n = 410*5;
const double inf = 1e18;
typedef pair<double, int> pdi;
struct node { double x, y;int num; };
struct edge{int to;double cost;};
vector<edge> G[max_n];
vector<node> ns;
double d[max_n];
int n, air, a, b;

void init() {
    for (int i = 0;i <= n * 5 + 10;i++)G[i].clear();
    ns.clear();
}

void dijstra(int s) {
    fill(d, d + n * 5, inf);
    priority_queue<pdi, vector<pdi>, greater<pdi>> que;
    d[s] = 0;que.push({ d[s], s });
    while (!que.empty()) {
        pdi p = que.top();que.pop();
        if (p.first > d[p.second])continue;
        d[p.second] = p.first;
        for (int i = 0;i < G[p.second].size();i++) {
            edge& e = G[p.second][i];
            if (d[e.to] < p.first + e.cost)continue;
            d[e.to] = p.first + e.cost;
            que.push({ d[e.to],e.to });
        }
    }
}

double computdist(node n1,node n2) {
    return sqrt((n1.x - n2.x) * (n1.x - n2.x) + (n1.y - n2.y) * (n1.y - n2.y));
}

void deal(node& n1,node& n2,node& n3,node& n4,double road) {
    double len1, len2, len3;
    len1 = computdist(n1, n2);
    len2 = computdist(n1, n3);
    len3 = computdist(n2, n3);
    G[n1.num].push_back({ n2.num,road * len1 });
    G[n2.num].push_back({ n1.num,road * len1 });
    G[n1.num].push_back({ n3.num,road * len2 });
    G[n3.num].push_back({ n1.num,road * len2 });
    G[n2.num].push_back({ n3.num,road * len3 });
    G[n3.num].push_back({ n2.num,road * len3 });
    if (len1 >= len2 && len1 >= len3) {
        n4.x = n1.x + n2.x - n3.x;
        n4.y = n1.y + n2.y - n3.y;
    }
    else if (len2 >= len1 && len2 >= len3) {
        n4.x = n1.x + n3.x - n2.x;
        n4.y = n1.y + n3.y - n2.y;
    }
    else {
        n4.x = n2.x + n3.x - n1.x;
        n4.y = n2.y + n3.y - n1.y;
    }
    G[n4.num].push_back({ n3.num,len1 * road });
    G[n3.num].push_back({ n4.num,len1 * road });
    G[n4.num].push_back({ n1.num,len3 * road });
    G[n1.num].push_back({ n4.num,len3 * road });
    G[n4.num].push_back({ n2.num,len2 * road });
    G[n2.num].push_back({ n4.num,len2 * road });
}

int main() {
    ios::sync_with_stdio(0);
    int t;cin >> t;
    while (t--) {
        cin >> n >> air >> a >> b;
        init();int total = 0;
        for (int i = 1;i <= n;i++) {
            vector<node> nn(4);double road;
            cin >> nn[0].x >> nn[0].y >> nn[1].x >> nn[1].y >> nn[2].x >> nn[2].y >> road;
            nn[0].num = ++total;nn[1].num = ++total;nn[2].num = ++total;nn[3].num = ++total;
            deal(nn[0], nn[1], nn[2], nn[3], road);
            for (int j = 0;j < ns.size();j++) {
                node& cur = ns[j];
                for (int k = 0;k < 4;k++) {
                    double dist = computdist(cur, nn[k]);
                    G[cur.num].push_back({ nn[k].num,dist * air });
                    G[nn[k].num].push_back({ cur.num,dist * air });
                }
            }while (!nn.empty()) {
                ns.push_back(nn.back());
                nn.pop_back();
            }
        }
        double ans = inf;
        for (int i = 1;i <= 4;i++) {
            dijstra(4 * a - 4 + i);
            for (int j = 1;j <= 4;j++)
                ans = min(ans, d[4 * b - 4 + j]);
        }
        cout << fixed << setprecision(1) << ans << endl;
    }
}

看别的题解，代码似乎精简许多？！不说了，去学习