파티

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

1238번: 파티

문제요약:

마을개수, 도로개수(단방향), 파티가 열리는 마을 세개가 주어지고 도로마다 걸리는 시간들이 주어졌을때, 각 마을에서 출발하는 사람들중에 파티하는마을에 들렸다가 집에 가는 시간이 가장 오래걸리는 사람의 이동시간을 구하여라

 

난이도:

골드3

 

소요시간:

15분

 

제출횟수:

2회

 

1차코딩:

import sys
import heapq as hp
input = sys.stdin.readline

n,m,x = map(int,input().split())
INF = int(1e9)
graph = [[] for _ in range(1+n)]

for _ in range(m):
    s,e,c=  map(int,input().split())
    graph[s].append([e,c])

def dijkstra(start):
    distance= [INF]*(n+1)
    distance[start] = 0
    q = [[0,start]]

    while q:
        dist,now = hp.heappop(q)
        if dist>distance[now]:
            continue

        for i in graph[now]:
            cost = dist +i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                hp.heappush(q,[cost,i[0]])
    return distance

x_distance = dijkstra(x)
print(max([x_distance[i] +dijkstra(i)[x] for i in range(1,n+1)]))

사실 굉장히 기본적인 다익스트라 문제라고 생각하고 제출하고 난이도를 확인해보니 골드3이길래 생각보다 높다고 생각했었는데, 끝나고 질문게시판을 살펴보니 훨씬 빠르게 푸는 방법이 있어 다시 소개하려고 글을 씁니다.

원래 처음에 생각했던건 파티하는 x마을에서부터 다른마을로 가는것은 다익스트라 한번이면 되니까 저장 하고 나머지 즉 x마을로 가는것은 그냥 낭비지만 다른마을로 부터 다익스트라를 하나씩 다 했다 하지만 이렇게 할 필요 없이 간선들의 방향을 반대로 뒤집은 다음에 다익스트라를 x마을기준으로 하면 이번엔 그 distance값들이 사실은 x마을로 가는것이기 때문에 두번의 다익스트라로 풀 수 있습니다. 아마 출제자의 의도는 이것이었을것 같습니다. 

 

두번째 코드:

import sys
import heapq as hp
input = sys.stdin.readline

n,m,x = map(int,input().split())
INF = int(1e9)
graph1 = [[] for _ in range(1+n)]
graph2 = [[] for _ in range(1+n)]

for _ in range(m):
    s,e,c=  map(int,input().split())
    graph1[s].append([e,c])
    graph2[e].append([s,c])

def dijkstra(start,graph):
    distance= [INF]*(n+1)
    distance[start] = 0
    q = [[0,start]]

    while q:
        dist,now = hp.heappop(q)
        if dist>distance[now]:
            continue

        for i in graph[now]:
            cost = dist +i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                hp.heappush(q,[cost,i[0]])
    return distance

go_x = dijkstra(x,graph1)
back_x = dijkstra(x,graph2)

print(max([go_x[i]+back_x[i] for i in range(1,n+1)]))

그리고 아래는 두 코드의 소요시간 입니다.