[백준] [최단경로] [다익스트라] [플로이드워셜] 11265. 끝나지 않는 파티

11265. 끝나지 않는 파티

11265번: 끝나지 않는 파티

 

• 내 풀이
  • 풀이 참고
  • 다익스트라
    • 처음에 dfs로 풀고 시간초과 발생
    • 이후 다익스트라 heap쓴 뒤에도 시간초과 
  • 시간초과 이유
    • 도착지점만 확인하는것이 아니라 출발지에서 모든 파티장으로의 최단거리를 한번에 계산
    • → 나중에 같은 출발지가 나오면 다시 dijk() 도는것이 아니라 재사용 할 수 있게 저장해놔야함

import heapq

n,m=map(int,input().split())

graph=[[0]+list(map(int,input().split())) for _ in range(n)]
graph.insert(0,[0 for i in range(n+1)])


def dijk(start):
    heapq.heappush(q, (0, start))
    result[start]=0
    
    while q:
        t,x=heapq.heappop(q)
        if result[x]<t: continue
    
        for i in range(1,n+1):
            if x==i: continue
            tmp=t+graph[x][i]
            #해당 시간 값보다 작아지는 경우만 
            if tmp<result[i]:
                result[i]=tmp
                heapq.heappush(q, (tmp, i))

    answer[start]=result
    check(result)

def check(result):
    global end
    global time
    if result[end]<=time:
        print("Enjoy other party")
    else:
        print("Stay here")
    

answer=[[] for _ in range(n+1)]
for i in range(m):
    #현재위치, 도착위치, 시간
    start, end, time=map(int,input().split())
    q=[]
    result=[int(1e9) for _ in range(n+1)]
    if answer[start] !=[]: #비어있지 않으면 이미 구해져있는 값
        check(answer[start])
    else:
        dijk(start)

 

• 다른 사람 풀이
  •  플로이드 워셜
  • 모든 노드의 최단경로를 계산해야 하므로 플로이드 워셜 알고리즘을 사용

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

for _ in range(m):
    a, b, time = map(int, input().split())
    if graph[a-1][b-1] <= time:
        print('Enjoy other party')
    else:
        print('Stay here')