2023 하계모각코 5회차 개인 목표 및 결과

일시

2023-08-05 13:00~ 16:00

목표

5회차에서는 4회차에 이어 다익스트라 알고리즘 문제를 풀어볼 생각이다.

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

13424번: 비밀 모임

결과

import sys; ssr = sys.stdin.readline

def floyd_Warshall_algorithm(_graph, _N, _M, _inf=1e15):
    _matrix = [[0 if i == j else _inf for i in range(_N + 1)] for j in range(_N + 1)]

    for _node_data in _graph:
        _matrix[_node_data[0]][_node_data[1]] = min(_node_data[2], _matrix[_node_data[0]][_node_data[1]])

    for k in range(1, _N + 1):
        for i in range(1, _N + 1):
            for j in range(1, _N + 1):
                _matrix[i][j] = min(_matrix[i][j], _matrix[i][k] + _matrix[k][j])

    return _matrix

T = int(ssr())
for _ in range(T):
    V, E = map(int, ssr().split())
    graph = []
    for _ in range(E):
        t1, t2, t3 = map(int, ssr().split())
        graph.append([t1, t2, t3])
        graph.append([t2, t1, t3])
    mat = floyd_Warshall_algorithm(graph, V, E)
    Q = int(ssr())
    q_list = list(map(int, ssr().split()))
    ans = 0
    ans_val = 10 ** 10
    for i in range(1, V + 1):
        i_val = 0
        for j in q_list:
            i_val += mat[j][i]
        if i_val < ans_val:
            ans_val = i_val
            ans = i
    print(ans)