[백준] 12908 텔레포트 3

좌표 6개 + 도착지점 1개 = 총 7개다

그럼 7!로 모든 순서를 보자 => next_permutation을 이용해서..!

좌표에 갈때는 map을 이용해서 순간이동을 시켜주고 +10 시켜줬다

마지막 도착지에 도착하면 그만 본다

소스코드

#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include <vector>
using namespace std;
#define ll long long
vector<ll> vt(7);
vector<pair<ll, ll>> arr(7);
map<int, pair<ll, ll>> mp;
ll sx, sy, ex, ey, ans = 1e15;
ll dist(ll x1, ll y1, ll x2, ll y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
    scanf(" %lld %lld %lld %lld", &sx, &sy, &ex, &ey);
    vt[6] = 6; arr[6] = { ex,ey };
    for (ll i = 0; i < 6; i++) {
        ll x, y; scanf(" %lld %lld", &x, &y);
        vt[i] = i;  arr[i] = { x,y };
    }
    for (ll i = 0; i < 6; i++) {
        if (i & 1) mp[i] = arr[i - 1];
        else mp[i] = arr[i + 1];
    }
    do {
        ll temp = 0;
        ll px = sx, py = sy;
        for (ll i = 0; i < 7; i++) {
            temp += dist(px, py, arr[vt[i]].first, arr[vt[i]].second);
            if (vt[i] == 6) break;
            temp += 10; 
            px = mp[vt[i]].first;
            py = mp[vt[i]].second;
        }
        ans = min(ans, temp);
    } while (next_permutation(vt.begin(), vt.end()));
    printf("%lld\n", ans);
}