🔥

문제

정올이는 GSHS에서 연구활동 때문에 교수님을 뵈러 A대학교를 가려고 한다.
출발점과 도착점을 포함하여 중간 지역은 n개이고, 한 지역에서 다른 지역으로 가는 방법이 총 m 개이다.
각 방법으로 지역 사이를 이동하는데는 어느 정도 비용이 필요하고, 한 지역에서 다른 지역으로 가는 어떠한 방법이 존재하면 같은 방법과 비용을 통해 역방향으로 갈 수 있다.
GSHS는 지역 1이고 A대학교는 지역 n이라고 할 때 대학까지 최소 비용을 구하여라.

n은 10 이하, m은 30 이하, 그리고 한 지역에서 다른 지역으로 가는 데에 필요한 비용은 200 이하 자연수이며 정점a->정점b로의 간선이 여러 개 있을 수 있으며, 자기 자신으로 가는 간선을 가질 수도 있다.

입력

첫 번째 줄에는 정점의 수 n과 간선의 수 m이 공백으로 구분되어 입력된다. 다음 줄부터 m개의 줄에 걸쳐서 이동할 수 있는 두 지역의 번호와 이동하는데 드는 비용이 입력된다.

출력

대학까지 가는 데 드는 최소 비용을 출력한다. 만약 갈 수 없다면 “-1”을 출력해라.

예제 1 입력

5 14
1 3 22
1 4 164
4 4 26
3 5 133
2 2 95
5 5 96
3 4 146
4 2 83
3 4 77
5 4 71
2 4 137
2 4 129
5 4 110
3 5 115

예제 1 출력

137

예제 2 입력

5 14
5 5 21
5 2 20
1 1 158
3 4 122
1 3 169
3 4 81
2 1 85
2 1 123
3 5 87
5 3 112
2 5 86
4 1 114
2 5 89
5 2 165

예제 2 출력

105

Source

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

edge = [[] for _ in range(n + 1)]

for i in range(m):
	u, v, cost = map(int, input().split())
	edge[u].append((v, cost))
	edge[v].append((u, cost))

minDis = [0 for _ in range(n + 1)]

def dfs(v, d):
	# 이미 v에 도달하는 dist가 현재 d값보다 작다면
	# 탐색을 수행할 필요가 없음
	if(minDis[v] != 0 and minDis[v] < d):
		return
	minDis[v] = d

	for _u, _cost in edge[v]:
		dfs(_u, d + _cost)

dfs(1, 1)

print(minDis[n] - 1)

참고