[BOJ 9370] 미확인 도착지 (c++)

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

틀린 풀이

#include <bits/stdc++.h>
using namespace std;
/**
 * 같은 비용의 여러 경로가 있을 수 있다.
 * 그래서 하나의 경로로 갈 수 있도록 강제하는 방식이 필요하다.
 */

int n, m, t;
int s, g, h;
vector<pair<int, int>> edges[2001];
int dist[2001];
int parent[2001];
vector<int> candidates;

bool calculate(int start) {
  while (1) {
    if (start == parent[start]) {
      break;
    }
    if ((start == g && parent[start] == h) ||
        (start == h && parent[start] == g)) {
      return true;
    }
    start = parent[start];
  }
  return false;
}

void dijkstra() {
  priority_queue<pair<int, int>> pq;
  pq.push({0, s});
  dist[s] = 0;

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

    for (int i = 0; i < edges[now].size(); i++) {
      int next = edges[now][i].first;
      int nCost = edges[now][i].second;
      if (dist[next] > cost + nCost) {
        dist[next] = cost + nCost;
        parent[next] = now;
        pq.push({-(cost + nCost), next});
      }
    }
  }
}
void solution() {
  int T;
  cin >> T;
  for (int i = 0; i < T; i++) {
    cin >> n >> m >> t;
    cin >> s >> g >> h;
    candidates.clear();
    for (int j = 0; j < 2001; j++) {
      dist[j] = INT_MAX;
      edges[j].clear();
      parent[j] = j;
    }
    for (int j = 0; j < m; j++) {
      int a, b, d;
      cin >> a >> b >> d;
      edges[b].push_back({a, d});
      edges[a].push_back({b, d});
    }
    for (int j = 0; j < t; j++) {
      int x;
      cin >> x;
      candidates.push_back(x);
    }

    dijkstra();
    vector<int> answer;

    for (int j = 0; j < candidates.size(); j++) {
      if (calculate(candidates[j])) {
        answer.push_back(candidates[j]);
      };
    }
    sort(answer.begin(), answer.end());
    for (int j = 0; j < answer.size(); j++) {
      cout << answer[j] << " ";
    }
    cout << '\n';
  }
}

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

  // input();
  solution();
  return 0;
}

• 처음에는 단순하게 한번의 다익스트라를 순회하면서 지나쳐온 경로를 parent배열에 저장하였다.
• 그 후, 후보들 중에서 g, h를 경로 중에 가지고 있는 경우를 출력해주었다.

만약 같은 비용의 경로가 여러개라면, g, h를 지나온 코드로 parent를 지정할 지는 해당 코드를 통해서는 할 수 없다.
즉, 10의 비용이지만 g-h를 경로중에 포함하고 있는 경로와, 포함하지 않는 경로가 있다면, 다익스트라를 통해 둘 중에 어떤 경로가 선택될지는 알 수 없다.

정답 풀이

#include <bits/stdc++.h>
using namespace std;

int n, m, t;
int s, g, h;
vector<pair<int, int>> edges[2001];
int dist[2001];
int dist2[2001];
vector<int> candidates;

void dijkstra() {
  priority_queue<pair<int, int>> pq;
  pq.push({0, s});
  dist[s] = 0;

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

    for (int i = 0; i < edges[now].size(); i++) {
      int next = edges[now][i].first;
      int nCost = edges[now][i].second;
      if (dist[next] > cost + nCost) {
        dist[next] = cost + nCost;
        pq.push({-(cost + nCost), next});
      }
    }
  }
}

void dijkstra2(int start) {
  priority_queue<pair<int, int>> pq;
  pq.push({0, start});
  dist2[start] = 0;

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

    for (int i = 0; i < edges[now].size(); i++) {
      int next = edges[now][i].first;
      int nCost = edges[now][i].second;
      if (dist2[next] > cost + nCost) {
        dist2[next] = cost + nCost;
        pq.push({-(cost + nCost), next});
      }
    }
  }
}

void solution() {
  int T;
  cin >> T;
  for (int i = 0; i < T; i++) {
    cin >> n >> m >> t;
    cin >> s >> g >> h;
    candidates.clear();
    int edgeDist;
    for (int j = 0; j < 2001; j++) {
      dist[j] = INT_MAX;
      edges[j].clear();
    }
    for (int j = 0; j < m; j++) {
      int a, b, d;
      cin >> a >> b >> d;
      if (a == g && b == h || a == h && b == g) {
        edgeDist = d;
      }
      edges[b].push_back({a, d});
      edges[a].push_back({b, d});
    }
    for (int j = 0; j < t; j++) {
      int x;
      cin >> x;
      candidates.push_back(x);
    }

    dijkstra();
    vector<int> answer;

    for (int j = 0; j < candidates.size(); j++) {
      for (int k = 0; k < 2001; k++) {
        dist2[k] = INT_MAX;
      }
      dijkstra2(candidates[j]);
      int dst1 = edgeDist + dist[h] + dist2[g];
      int dst2 = edgeDist + dist[g] + dist2[h];

      if (dst1 == dist[candidates[j]] || dst2 == dist[candidates[j]]) {
        answer.push_back(candidates[j]);
      }
    }
    sort(answer.begin(), answer.end());
    for (int j = 0; j < answer.size(); j++) {
      cout << answer[j] << " ";
    }
    cout << '\n';
  }
}

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

  // input();
  solution();
  return 0;
}

• 다익스트라를 추가로 한번 더 사용해서, 후보 정점들에서 h까지의 최단 거리, g까지의 최단 거리를 구해주었다.
• 이때, g-h사이의 거리 + 시작점에서의 g또는 h의 거리 + 후보 정점에서의 h또는 g의 거리가 첫번째로 구한 다익스트라의 최단 거리와 일치하다면, g-h를 통하는 최단거리 경로가 있다는 점에서 착안하였다.
• 즉 핵심 코드는 다음과 같다.

  int dst1 = edgeDist + dist[h] + dist2[g];
      int dst2 = edgeDist + dist[g] + dist2[h];

      if (dst1 == dist[candidates[j]] || dst2 == dist[candidates[j]]) {
        answer.push_back(candidates[j]);
      }

어렵진 않지만, 너무 단순하게 처음에 생각해서 헤매어버린 문제.. 예시 케이스 중에 같은 비용의 최단 경로가 여러개인 경우가 없어서 예시 케이스를 다 맞아버려 예외 케이스를 생각하기 어려웠다.