접근 특정한 노드에서 특정 노드까지 가는 최소 비용을 구하는 문제이다. 출발점에서 도착점까지 갈 수 있는 경우만 입력으로 오니 따로 예외처리를 신경쓰지 않고 다익스트라 알고리즘을 사용할 생각을 했다. 나의코드 import sys from heapq import heappush, heappop input = sys.stdin.readline n = int(input()) m = int(input()) INT = int(10e9) G = [[] for _ in range(n+1)] for i in range(m): s, f, value = map(int,input().split()) G[s].append((value,f)) def dik(start,finish): d = [INT] *(n+1) H = [] ..

접근 기존 문제를 풀면서 다익스트라 알고리즘에 익숙해졌다. 익숙해진 다익스트라 알고리즘으로 접근했다. 해당 문제에서 내가 주의있게 본 부분은 웜홀은 시간이 줄어든다는 것, 즉 음수의 가중치가 있다는 점이었다. 다익스트라 알고리즘에 대해 생각해보면 전통적인 방법, heap을 사용하는 방법, heap을 사용하는 방법에서 재방문을 허용하는지, 하지않는지 3가지 정도 방법을 나뉜다. 나는 보통 heap을 사용하며 재방문을 허용하는 방식으로 변형해서 다익스트라 알고리즘을 사용한다. 가중치가 그리디한 방식으로 주어질 때 동일한 성능을 보이고 만약 가중치가 무작위로 주어지는 경우까지 답을 구할 수 있기 때문이다. 음의 가중치가 주어지는 경우에도 성능은 좋지 않지만 (처음 최단거리라고 생각하고 관련된 edge를 모두 ..

접근 다익스트라 알고리즘을 이용해 특정 노드에서 특정 노드까지의 최단거리를 구한다. 나의 코드 import sys input = sys.stdin.readline from heapq import heappop,heappush v,e = map(int, input().split()) INF = sys.maxsize start = int(input()) G = [[] for _ in range(v+1)] def dik(start): d = [INF] * (v+1) H = [] heappush(H,(0,start)) d[start] = 0 while H: value,v1 = heappop(H) if d[v1] < value: continue for value2,v2 in G[v1]: nv = value+val..

접근 특정노드에서 특정노드까지 가는 최단거리가 필요하니 다익스트라 알고리즘을 사용해야함. 시작지점, v1, v2 기준의 거리를 구하고 s + v1 +v2 + t, s+v2+v1+t 까지의 거리를 구한다. 나의 코드 import sys input = sys.stdin.readline from heapq import heappush, heappop n, e = map(int,input().split()) INF = int(1e9) G = [[] for _ in range(n+1)] for _ in range(e): a, b ,c = map(int,input().split()) G[a].append((b,c)) G[b].append((a,c)) def dik(start): distance = [INF] * (..

접근 최단거리를 찾는 문제중에서 특정 정점에서 특정 정점까지 가는 문제라 bfs, 다익스트라 알고리즘으로 풀 생각을 했다. 가중치가 없어 bfs로도 풀수있겠다는 생각을 했지만 경로 알고리즘을 학습하고 싶어 시간 제한을 생각하지않고 다익스트라, 플로이드 워셜으로 풀어봤다. 플로이드 워셜(시간초과) import sys input = sys.stdin.readline n, m , t = map(int,input().split()) M = [[101 for _ in range(n)] for _ in range(n)] for i in range(m): s, f, v = map(int,input().split()) M[s-1][f-1] = v for i in range(n): M[i][i] = 0 for k in ..