[SWEA/Python] 1795. 인수의 생일 파티

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. 다익스트라 알고리즘 사용
2. 처음에는 모든 인접한 노드의 시간을 갱신하고, 그 중 최소값을 찾아서 이동하였는데 시간초과
3. bfs를 사용해서 시간이 더 줄어드는 경로로만 이동하는 방식으로 구현했더니 통과하였다.

 

📌 코드

import sys
sys.stdin = open('input.txt')

def dijkstra(start, end):
    time[start] = 0

    for _ in range(N):
        min_idx = -1
        min_time = float('inf')
        for v in range(1, N+1):
            if not visited[v] and time[v] < min_time:
                min_time = time[v]
                min_idx = v
        
        if min_idx == end:
            return time[min_idx]

        visited[min_idx] = 1

        for w, wtime in town[min_idx]:
            if not visited[w]:
                time[w] = min(time[w], time[min_idx]+wtime)


T = int(input())

for t in range(1, T+1):
    N, M, X = map(int, input().split())
    town = [[] for _ in range(N+1)]

    for _ in range(M):
        x, y, c = map(int, input().split())
        town[x].append((y, c))

    max_time = 0
    for s in range(1, N+1):
        if s != X:
            time = [float('inf') for _ in range(N+1)]
            visited = [0 for _ in range(N+1)]
            go = dijkstra(s, X)

            time = [float('inf') for _ in range(N+1)]
            visited = [0 for _ in range(N+1)]
            back = dijkstra(X, s)

            max_time = max(max_time, go + back)
    
    print('#{} {}'.format(t, max_time))

→ 1개 케이스에서 시간초과

 

from collections import deque
import sys
sys.stdin = open('input.txt')

def dijkstra(start, end):
    queue = deque()
    queue.append(start)

    time = [float('inf') for _ in range(N+1)]
    time[start] = 0

    while queue:
        v = queue.popleft()

        for w, wtime in town[v]:
            if time[v]+wtime < time[w]:
                time[w] = time[v]+wtime
                queue.append(w)

    return time[end]
    

T = int(input())

for t in range(1, T+1):
    N, M, X = map(int, input().split())
    town = [[] for _ in range(N+1)]

    for _ in range(M):
        x, y, c = map(int, input().split())
        town[x].append((y, c))

    max_time = 0
    for s in range(1, N+1):
        if s != X:
            go = dijkstra(s, X)

            back = dijkstra(X, s)

            max_time = max(max_time, go + back)
    
    print('#{} {}'.format(t, max_time))