iT邦幫忙

0

[一天至少一題直到 ICPC 開賽 #012] 解題:2D Traveling(沒發到12/21)

  • 分享至 

  • xImage
  •  

2D Traveling

  • 昨天晚上的時候有寫了,但忘記發出來

題目連結

  • 在起點與終點找到離主城最近的距離(這裡稱作是a)

a 的求法 = 起點與最近的主城距離 + 終點與最近的主城之距離 (不可是相同的主城)

不通過主城最近的距離 ==> 起點與終點的直線距離

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#define ll long long

using 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;
}

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言