살짝 응용 다익스트라 (살응다)

다를 조금 응용해볼까?

  • 문제

    방향성이 없는 그래프가 주어진다. 세준이는 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)

    출력

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

문제 아이디어

  • 문제의 요점은 주어진 v1과 v2를 지나는 최단 경로의 길이를 출력하는 것이다. 또한, 1번에서 출발하여 N번 도착지로 가는 방향도 정해져있다. 우리는 도착지까지 가는 사이에 저 2개의 경로를 껴넣으면 된다.
  • 주어지는 경로지는 중복이 되지 않음으로, 다음과 같이 2가지의 방법이 있다는 것을 알 수 있다.
    • 1) 출발지 -> v1 -> v2 -> 도착지
    • 2) 출발지 -> v2 -> v1 -> 도착지
  • 1번의 경우를 봤을 때, v1을 가는데 도중에 v2가 있어서 왔다갔다 하는 반례가 있지 않냐? 라고 할 수 있는데, 그것의 경우는 2번에서 카운트를 해주기 때문에 생각할 필요가 없다.
  • 따라서 우리는 1번의 경우와 2번의 경우를 구해서, 더 작은 값을 가져가면 답을 얻을 수 있다.

문제 풀이

  • 우리가 해야 될 일은 위에서 명시해 놓은 1) 과 2) 를 코드로 구현하면 된다. 최단거리를 구하는 방법은 다익스트라 를 참고하면 된다.
    • 출발지를 기준으로 다익스트라
    • v1을 기준으로 다익스트라
    • v2를 기준으로 다익스트라
  • 15번째 줄부터 시작하는vector<ll> djk(int startNode) 함수는 다익스트라를 구하는 함수이다.
  • 53~55번째 줄부터는 위의 3가지 다익스트라 비용을 저장하는 벡터이다.
  • 만약에 저 중에 하나라도 INF와 같은 값이 나온다는 것은, 경로가 없다는 것을 뜻한다.
  • 문제가 어려운 것처럼 보이지만!? 사실은 짜장면에 고추가루 뿌리는 느낌의 그런,,,, 알죠?

Code

오늘의 Tip!

너 for문 문제있어?

  • Python을 해본 사람이라면, Python 문법중에 for num in num_list 의 편리성을 알 것이다. 인덱스로 하나하나 접근하지 않고, 바로 원소를 뽑아낼 수 있는 for 문 말이다! C++ 에도 있다! 절망하지 마라! C++에서는 다음과 같은 문법을 통해 원소를 뽑아낼 수 있다.

  • 내가 벡터내의 자료형을 매번 명시해준다면 auto를 안써도 된다. 알아서 자료형을 찾아서 맞게끔 해주는게 auto인데, 시간이 아주 조금 더 걸리는데 (사실 알골 푸는데는 큰 지장이 없음) 취향에 맞게끔 사용하면 된다.

  • 참조의 경우에는 C++ 여러곳에서 아주 유용하게 쓰인다. 참조에 대해서 잘 모른다면, 앞으로 포스팅할 포인터&참조 포스팅을 참고하면 될 것이다.