2D Traveling

题目连结

a 的求法 = 起点与最近的主城距离 + 终点与最近的主城之距离 (不可是相同的主城)

不通过主城最近的距离 ==> 起点与终点的直线距离

#include <iostream>#include <map>#include <vector>#include <algorithm>#include <cmath>#define ll long longusing namespace std;ll distance(ll x1, ll x2, ll y1, ll y2){    return abs(x1 - x2) + abs(y1 - y2);}int main(int argc, char const *argv[]){    ll t = 0;    cin >> t;    while (t--)    {        ll n, m, s, f;        cin >> n >> m >> s >> f;        vector<pair<int, int>> v(n + 1);        for (int i = 1; i <= n; i++)        {            cin >> v[i].first >> v[i].second;        }        ll d;        d = distance(v[s].first, v[f].first, v[s].second, v[f].second);        ll ans[2];        ans[0] = 1000000000000;        ans[1] = 1000000000000;        for (int i = 1; i <= m; i++)        {            ans[0] = min(ans[0], distance(v[i].first, v[s].first, v[i].second, v[s].second));            ans[1] = min(ans[1], distance(v[i].first, v[f].first, v[i].second, v[f].second));        }        ans[0] = min(ans[0] + ans[1], d);        cout << ans[0] << endl;    }    return 0;}