[BOJ] 1504 - 특정한 최단 경로

https://www.acmicpc.net/problem/1504

BOJ - 특정한 최단 경로

문제 유형: 최단 경로, 다익스트라, 그래프

문제 난이도: Gold IV

시간 제한: 1초

메모리 제한: 256MB

 

문제

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

 

풀이

반드시 두 점을 거쳐서 N에 도달하려면, 두 가지 경로가 있다.

두 점을 각각 stop1, stop2라 해보자.

1 -> stop1 -> stop2 -> N

1 -> stop2 -> stop1 -> N

즉, 경로를 작은 단위로 쪼개서 합을 더한 것들 중 더 큰 작은걸 출력하면 된다.

 

두 구간의 거리는 향상된 다익스트라를 이용했다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n, e;

int dijkstra(int src, int dst, vector<vector<pair<int, int>>> graph) {
  vector<int> dist(n + 1, INT_MAX);
  dist[src] = 0;
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>>
      pq;
  pq.push({0, src});

  while (!pq.empty()) {
    auto curr = pq.top();
    pq.pop();
    int distance = curr.first;
    int node = curr.second;
    if (distance > dist[node])
      continue;

    for (const auto &next : graph[node]) {
      if (distance + next.second < dist[next.first]) {
        dist[next.first] = distance + next.second;
        pq.push({distance + next.second, next.first});
      }
    }
  }

  return dist[dst] == INT_MAX ? -1 : dist[dst];
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> e;
  vector<vector<pair<int, int>>> graph(n + 1);

  int src, dst, weight;
  for (int i = 0; i < e; ++i) {
    cin >> src >> dst >> weight;
    graph[src].push_back({dst, weight});
    graph[dst].push_back({src, weight});
  }

  int stop1, stop2;
  cin >> stop1 >> stop2;

  int intersection = dijkstra(stop1, stop2, graph);
  if (intersection == -1) {
    cout << "-1\n";
    return 0;
  }

  int path1_start = dijkstra(1, stop1, graph);
  int path1_end = dijkstra(stop2, n, graph);

  int path2_start = dijkstra(1, stop2, graph);
  int path2_end = dijkstra(stop1, n, graph);

  int ans1 = (path1_start < 0 || path1_end < 0)
                 ? -1
                 : path1_start + intersection + path1_end;
  int ans2 = (path2_start < 0 || path2_end < 0)
                 ? -1
                 : path2_start + intersection + path2_end;

  if (ans1 == -1 && ans2 == -1) {
    cout << "-1\n";
  } else if (ans1 == -1) {
    cout << ans2 << "\n";
  } else if (ans2 == -1) {
    cout << ans1 << "\n";
  } else {
    cout << min(ans1, ans2) << "\n";
  }

  return 0;
}