-
Notifications
You must be signed in to change notification settings - Fork 6
/
pokemongogo.py
26 lines (26 loc) · 1018 Bytes
/
pokemongogo.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import sys; input = sys.stdin.readline
from itertools import combinations
INF = 1e18
poke = [(0, 0, '@')]; rev = {'@': 0}
for _ in range(N:=int(input())):
x, y, p = input().strip().split(); x, y = int(x), int(y)
if p not in rev: rev[p] = len(rev)
poke.append((x, y, p))
G = [[INF]*(N+1) for _ in range(N+1)]
for i in range(N):
x1, y1, _ = poke[i]
for j in range(i+1, N+1):
x2, y2, _ = poke[j]; G[i][j] = G[j][i] = abs(x1-x2) + abs(y1-y2)
n = len(G); C = [[INF for _ in range(n)] for _ in range(1<<len(rev))]; C[1][0] = 0
for s in range(1, n):
for S in combinations(range(1, n), s):
k = 1
for i in S: k |= 1<<rev[poke[i][2]]
for i in S:
if i == 0: continue
p = k^(1<<rev[poke[i][2]])
C[k][i] = min(C[k][i], C[p][0]+G[0][i])
for j in S:
if j != i: C[k][i] = min(C[k][i], C[p][j]+G[j][i])
c, g = C[-1], G[0]; nxt = min((c[i]+g[i], i) for i in range(n))[1]
print(c[nxt]+g[nxt])