[백준/C++] 1504번. 특정한 최단 경로

[백준/C++] 1504번. 특정한 최단 경로

1. 문제

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

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

2. 입력

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

3. 출력

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

4. 풀이

• 다익스트라 문제
• 1번부터 N번까지 가는 최단 경로를 가는데 v₁과 v₂를 지나야 한다.
• 두 가지 경우가 가능하다.
  • 1 → v₁ → v₂ → N
  • 1 → v₂ → v₁ → N
• 출발지를 다르게 해서 다익스트라를 해주면 된다.
• 먼저 1번에서 v₁과 v₂로 가는 최단 경로를 구한다.
  • dijkstra(1)을 한다.
  • 1번 경로에 d[v₁] 값을 더하고 2번 경로에 d[v₂] 값을 더한다.
• v₁에서 v₂로 가는 경로와 v₂에서 v₁로 가는 최단 경로를 구한다.
• 방향성이 없는 그래프이기 때문에 둘의 값이 같다.
  • dijkstra(v₁)을 한다.
  • 1번 경로와 2번 경로에 모두 d[v₂] 값을 더한다.
• v₁에서 N으로 가는 경로와 v₂에서 N으로 가는 최단 경로를 구한다.
• 방향성이 없는 그래프이기 때문에 N을 기준으로 다익스트라를 하면 1번 동작으로 둘 다 구할 수 있다.
  • dijkstra(N)을 한다.
  • 1번 경로에 d[v₂] 값을 더하고 2번 경로에 d[v₁] 값을 더한다.
• 둘 중 최소 경로를 출력한다.

5. 처음 코드와 달라진 점

• 양방향 그래프 처리를 안 해줘서 추가해주었다.
• INF 값을 너무 크게 설정해서 int 범위를 초과해서 INF 값을 수정해주었다.

6. 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 200001

using namespace std;

int n, e, v1, v2;
vector<pair<int, int> > graph[801];
int d[801];

void dijkstra(int start) {
  priority_queue<pair<int, int > > pq;
  d[start] = 0;
  pq.push(make_pair(0, start));

  while (!pq.empty()) {
    int dist = -pq.top().first;
    int now = pq.top().second;
    pq.pop();

    if (d[now] < dist) continue;
    for (int i = 0; i < graph[now].size(); i++) {
      int next = graph[now][i].first;
      int cost = dist + graph[now][i].second;

      if (cost < d[next]) {
        d[next] = cost;
        pq.push(make_pair(-cost, next));
      }
    }
  }
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int route1 = 0, route2 = 0;
  cin >> n >> e;
  for (int i = 0; i < e; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back(make_pair(b, c));
    graph[b].push_back(make_pair(a, c));
  }

  cin >> v1 >> v2;

  fill_n(d, 801, INF);
  dijkstra(1);

  route1 = d[v1];
  route2 = d[v2];

  fill_n(d, 801, INF);
  dijkstra(v1);

  route1 += d[v2];
  route2 += d[v2];

  fill_n(d, 801, INF);
  dijkstra(n);

  route1 += d[v2];
  route2 += d[v1];

  int answer = min(route1, route2);
  if (INF <=answer) cout << -1;
  else cout << answer;
}```