특정한 최단거리 (골드 4)

특정한 최단 경로 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

77113

20219

13713

24.717%

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제 입력 1 복사

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1 복사

7

 

---

# 풀이

 

(정답 확인 함)

 

이 문제는 가중치 그래프와 다익스트라 알고리즘을 이용하는 문제이다.

 

단순히 다익스트라만 구현 하는 것이 아닌 특정 노드 2개를 방문해야 할 때, 목적지 노드까지 구할 수 있는 가장 짧은 거리를 구해야 한다.

 

이때 경유해야 하는노드 v1, v2 를 거쳐 목적지(n노드) 까지 가는 경우의 수는 2가지 이다.

 

1. 출발노드(1노드) -> v1노드 -> v2노드 ->  n노드

a[v1] + b[v2] + c[n]

2. 출발노드(1노드) -> v2노드 -> v1노드 ->  n노드

a[v2] + c[v1] + b[n]

두가지의 경우의 수를 모두 알고리즘을 적용하여 후 그 리턴값을  min 함수로 비교하여 더 작은 수를 반환하도록 하였다.

a = solution(1) # 1부터 n까지 

 

b = solution(v1) # v1부터 n까지 

 

c = solution(v2) # v2부터 n까지 

# 1-v1-v2-n 경우와 1-v2-v1-n 경우중 최단 거리를 구한다.

answer = min(a[v1] + b[v2] + c[n], a[v2] + c[v1] + b[n])

answer 함수의 파라미터는 출발지를 나타냄으로 각 코드당 가지는 의미를 주석으로 처리하였다.

 

이부분을 통해 다익스트라의 값을 응용 하는 방법을 하나 배운 셈이다.

 

solution 함수는 이전 다익스트라 알고리즘 개요에서 다룬 내용과 같으므로 정의 부분은 생략하였다.

 

정리

 

1. 파라미터값 (출발지)와 키값을 이용하여 원하는 특정 경로에 다익스트라를 적용할 수 있는 방법을 알았다.