ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 31219 |
문제명 | 세계 일주 |
레벨 | 골드 4 |
분류 |
TSP |
시간복잡도 | O(n*n!) |
인풋사이즈 | n<=10 |
사용한 언어 | Python 3.11 |
제출기록 | 33240KB / 7116ms |
최고기록 | 7116ms |
해결날짜 | 2024/01/08 |
"""Solution code for "BOJ 31219. 세계 일주".
- Problem link: https://www.acmicpc.net/problem/31219
- Solution link: http://www.teferi.net/ps/problems/boj/31219
Tags: [tsp]
"""
import math
import itertools
INF = float('inf')
def main():
n = int(input())
coords = [[int(x) for x in input().split()] for _ in range(n)]
answer = INF
for path in itertools.permutations(coords):
tot_dist = 0
for p, q in itertools.pairwise([*path, path[0]]):
tot_dist += math.dist(p, q)
if tot_dist >= answer:
break
else:
answer = tot_dist
print(answer)
if __name__ == '__main__':
main()