BOJ - 3075 - Astromeeting

import sys

INF = 1e8
_INF = 1e10

def solution():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, P, Q = map(int, sys.stdin.readline().split())

        people = []
        for _ in range(N):
            people.append(int(sys.stdin.readline()))

        galaxy = [[_INF for _ in range(P)] for _ in range(P)]

        for _ in range(Q):
            i, j, d = map(int, sys.stdin.readline().split())
            galaxy[i-1][j-1] = min(d, galaxy[i-1][j-1])
            galaxy[j-1][i-1] = min(d, galaxy[j-1][i-1])

        for i in range(P):
            galaxy[i][i] = 0

        for k in range(P):
            for i in range(P):
                if galaxy[i][k] == _INF: continue
                for j in range(P):
                    if galaxy[k][j] == _INF: continue
                    galaxy[i][j] = min(galaxy[i][j], galaxy[i][k] + galaxy[k][j])

        planet = -1
        ret = _INF
        for i in range(P):
            dist = 0
            for j in people:
                dist += (galaxy[i][j-1] * galaxy[i][j-1])
            if dist < ret:
                planet = i + 1
                ret = dist

        print(planet, ret)

solution()

https://www.acmicpc.net/problem/3075