문제

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

처음에 문제 대충읽고 그냥 다익스트라 알고리즘으로 풀면 쉽게 풀리는 문제아닌가?? 이게 왜 Gold3 ?? 라는 생각을 했는데 잘 읽어보니까 특정 노드까지 "왕복한 거리"를 구하는 문제라는 점에서 일반적인 다익스트라 알고리즘 문제랑 차이가 있었다~!

내 코드

import sys ,heapq
node,edge,dstnt=map(int,input().split())
INF=int(1e9)
graph=[[] for _ in range(node+1)]

for _ in range(edge):
    a,b,c=map(int,sys.stdin.readline().strip().split())
    graph[a].append((b,c))


print(graph)

def dijkstra(start):
    q=[]
    heapq.heappush(q,(0,start))
    # 시작 노드 처리
    distance[start]=0

    while q:
        dist,now=heapq.heappop(q)
        print(dist,now)
        if dist>distance[now]:
            continue
        for n in graph[now]:
            cost=dist+n[1]
            if distance[n[0]] > cost:
                distance[n[0]]=cost
                heapq.heappush(q,(cost,n[0]))

dist_ans=[]
go_back_home=[]
for i in range(1,node+1):
    distance=[INF]*(node+1)
    dijkstra(i)
    if i==dstnt:
        go_back_home=distance[1:]
    dist_ans.append(distance[dstnt])

# 왕복한 거리 처리
ans=[]
for go,back in zip(dist_ans,go_back_home):
    ans.append(go+back)

print(max(ans))

다익스트라 알고리즘으로 각 시작노드별로 다른 노드들까지의 거리를 구한 후 입력받은 목적지 노드까지의 거리만 추출해서 dist_ans 리스트에 담는다.

목적지 노드에서 다시 시작노드로 돌아오는 최단거리는 위의 과정에서 이미 구한 값이기 때문에 따로 저장해두었다가 더해서 왕복한 거리를 구해주면 된다~