(c++) 다익스트라 문제 1504번: 특정한 최단 경로

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

1504번: 특정한 최단 경로

 

 

---

 

 

1504번: 특정한 최단 경로

 

일반적인 다익스트라 문제지만 정점과 간선을 여러 번 들릴 수 있고,

 

두 개의 정점을 꼭 들려서 최종 정점에 도달하여야 한다.

 

여러 가지 방법으로 풀 수 있지만

 

나는 다익스트라 3번을 사용하여 해결했다.

 

일단 무조건 1번 정점부터 마지막 번호의 정점으로 도착하는 경우이므로

 

두 가지 경우의 수를 도출할 수 있다.

 

두 가지 경우의 수

 

필수로 들려야 하는 정점 두 개를 v1, v2라고 했을 때

 

1. 1번 정점 → v1 → v2 → 마지막 정점

 

2. 1번 정점 → v2 → v1 → 마지막 정점

 

따라서 우리는 1번 정점의 다익스트라를 구한 후 아래 두 가지 경우를 저장한다.

 

1번 정점 → v1

1번 정점 → v2

 

그리고 v1에서 v2인 경우와 v1에서 마지막 정점인 경우 두 가지를 경우를 저장한다.

 

v1 → v2

v1 → 마지막 정점

 

마지막 다익스트라는 v2에서 v1, v2에서 마지막 정점인 경우를 구한다.

 

v2 → v1

v2 → 마지막 정점

 

출력 부분에서 경우의 수가 없는 부분은 -1을 출력하고

(프로그램 구조 상 경우의 수가 없는 부분을 먼저 해주는 것이 속도에서 유리하다.)

 

(1번 정점 → v1)  +  (v1 → v2)  +  (v2 → 마지막 정점)

 

(1번 정점 → v2)  +  (v2 → v1)  +  (v1 → 마지막 정점)

 

두 가지를 비교하여 작은 것을 출력하면 된다.

 

조심해야 하는 부분

 

INF로 설정한 값이 너무 크면 결과 값이 오버플로우가 나서 음수로 표기가 날 수 있다.

 

INF를 적당한 값으로 설정하거나 result 변수들을 long이나 long long으로 설정해주자.

 

#include <bits/stdc++.h>
#define INF 1e8

using namespace std;

int N, E, v1, v2;
vector<pair<int, int> > graph[801];

int dijkstra(int start, int end) {
  vector<int> dist(N + 1, INF);
  dist[start] = 0;
  priority_queue<pair<int, int> > pq;
  pq.push({0, start});
  while(!pq.empty()) {
    int cost = -pq.top().first;
    int here = pq.top().second;
    pq.pop();
    if(dist[here] < cost) continue;
    for (int i = 0; i < graph[here].size(); i++) {
      int there = graph[here][i].first;
      int nextDist = cost + graph[here][i].second;
      if (dist[there] > nextDist) {
        dist[there] = nextDist;
        pq.push(make_pair(-nextDist, there));
      }
    }
  }
  return dist[end];
}

int main(void) {
  cin >> N >> E;
  for (int i = 0; i < E; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back({b, c});
    graph[b].push_back({a, c});
  }
  cin >> v1 >> v2;

  int startV1 = dijkstra(1, v1);
  int startV2 = dijkstra(1, v2);

  int secondV1 = dijkstra(v1, v2);
  int endV1 = dijkstra(v1, N);

  int secondV2 = dijkstra(v2, v1);
  int endV2 = dijkstra(v2, N);
  
  long long result1, result2;
  result1 = startV1 + secondV1 + endV2;
  result2 = startV2 + secondV2 + endV1;
  
  long long result = min(result1, result2);

  if (result >= INF) {
    cout << "-1";
  } else {
    cout << result;
  }
}

 

 

위 코드는 다익스트라를 6번하는 것으로 속도 측면에서는 조금 부족할 수 있지만

 

9번 라인 매개변수를 int start 만 두고

 

return dist; 로 둔 후

 

각각의 다익스트라를 따로 변수를 두고 저장하여 꺼내쓰는 방법도 가능하다. (대신 메모리 부분은 감안해야 한다.)

 

vector<int> dist1(V + 1, INF);
dist1 = dijkstra(V1);