문제
양방향으로 이동이 가능한 그래프 정보가 정점수 N, 간선수 M 으로 주어진다.
M개의 간선중에 하나를 골라 비용을 절반(소숫점이하는 버림)으로 줄일수 있다고 할 때,
1번 정점으로부터 N번 정점까지의 최단거리를 구하는 프로그램을 작성하시오.
입력
첫 행에 N, M이 주어진다. ( 1< N <= 10), (1 <= M <= 30)
두 번째 행부터 M개의 행에 간선 정보 si, ei, wi 가 주어진다.
간선 정보는 자기 자신으로의 정보도 주어질수 있다.
또한 어떤 두 노드사이 정보가 여러 개 주어질 수 있음에 유의한다.
( 1 <= si, ei <= N), (1<= wi <= 200)
출력
M개의 간선중에 하나의 비용을 절반으로 줄여 1번에서 N번까지 최단경로를 구한 결과를 출력한다.
최단 경로를 구할 수 없는 경우 -1을 출력한다.
예제 #1
6 6
1 2 7
2 3 16
3 6 9
1 4 9
4 3 10
4 5 14
5 6 8
23
예제 #2
7 11
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40
114
출처
comkiwer
로그인해야 코드를 작성할 수 있어요.