1795. 인수의 생일 파티

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4xuqCqBeUDFAUx&categoryId=AV4xuqCqBeUDFAUx&categoryType=CODE&problemTitle=%EC%9D%B8%EC%88%98&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

def dij(s, N, adj, dist):
    U = [0] * (N + 1)  # visited 역할
    U[s] = 1 # 방문처리
    cnt = N - 1  # 남아있는 정점 수 (시작점 제외)
    while cnt > 0:  # 모든 정점을 돌 때까지 반복
        min_w = INF 
        w = 0  # 현재까지 발견한 최단 거리를 가지는 정점의 인덱스
        for i in range(1, N + 1):  # 모든 정점 순회 
            if U[i] == 0 and min_w > dist[i]:  # 방문하지 않은 곳 최단거리 갱신
                min_w = dist[i]  
                w = i  # 최단거리 인덱스 갱신
        U[w] = 1  # 최단거리인 정점 추가
 
        for v in range(1, N + 1): # w에 인접한 모든 정점 v 순회
            if 0 < adj[w][v] < INF:  # 자기자신과 무한대 제외(adj[w][v]는 정점 w에서 정점 v로 가는 간선의 가중치(거리))
                dist[v] = min(dist[v], dist[w] + adj[w][v])  # 현재까지 계산된 최단 거리 dist[v]와 새로 계산한 거리 dist[w] + adj[w][v] 중에서 더 작은 값을 dist[v]에 업데이트
        cnt -= 1 # 정점 수 하나 감소(정점 하나를 탐색했으니)
 
T = int(input())
for tc in range(1, T + 1):
    N, M, X = map(int, input().split())  # N 집 번호, M 도로 수, X 인수집
    INF = int(1e6)
    A = [[INF] * (N + 1) for _ in range(N + 1)]  # 인수의 집에서 돌아가는
    AA = [[INF] * (N + 1) for _ in range(N + 1)]  # 인수의 집으로 오는
     
    for i in range(N + 1):  # 인접 정보
        A[i][i] = 0
        AA[i][i] = 0
     
    for _ in range(M):  # 도로 정보
        x, y, c = map(int, input().split())  # 출발, 도착, 시간
        A[x][y] = c  # 출발, 도착
        AA[y][x] = c  # 도착, 출발
     
    D = [0] * (N + 1)  # 거리 정보
    DD = [0] * (N + 1)
     
    for i in range(N + 1):
        D[i] = A[X][i]  # 인수집에서 각 집으로 가는 초기 비용
        DD[i] = AA[X][i]  # 각 집에서 인수집으로 가는 초기 비용
     
    # 인수집에서 각 집으로 가는 최단 거리 계산
    dij(X, N, A, D)
     
    # 각 집에서 인수집으로 가는 최단 거리 계산
    dij(X, N, AA, DD)
     
    # 각 집에서 인수집까지 가는데 필요한 시간과 돌아오는데 필요한 시간을 합쳐서 최댓값을 찾음
    for i in range(1, N + 1):
        D[i] += DD[i]
     
    print(f'#{tc} {max(D[1:])}') # 0번 인덱스 제외하고 최댓값 구하기