[백준 / BOJ] C++ 9370 미확인 도착지

9370번: 미확인 도착지

 

문제

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

9370번: 미확인 도착지

 

 

풀이

먼저 가장 큰 접근법은 G-H는 반드시 지나야 하므로 S -> G -> H -> ? 또는 S -> H -> G -> ? 이 최단 경로여야 한다. 따라서 S -> G, S -> H, G -> H, G -> ?, H -> ? 의 최단 거리를 구해야 한다. 즉, 간선 거리는 항상 양수고 몇몇 정점간 거리를 구해야 하므로 다익스트라 알고리즘을 사용했다.

 

따라서 S -> G, S -> H, G -> H는 한 테스트 케이스 내에 계속 쓰이므로 미리 구해둔다. 그리고 목적지 후보 D를 하나 입력받을 때마다 S -> D의 최단 경로를 구한다. 또 H -> D, G -> D를 구해서 S -> G -> H -> D 또는 S -> H -> G -> D가 최단 경로와 같으면 ans 배열에 D를 추가해 준다. 오름차순으로 출력해야 하므로 정렬한 다음 차례대로 출력해 주면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int n, m, t, s, g, h;
vector<pair<int, int>> graph[2001];
vector<int> dist(2001, INF), visited(2001, 0);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void init() {
  for (int i = 1; i <= n; i++) {
    visited[i] = 0;
    dist[i] = INF;
  }
}

int dijkstra(int s, int e) {
  init();
  dist[s] = 0;
  pq.push({0, s});
  while (!pq.empty()) {
    int curr;
    do {
      curr = pq.top().second;
      pq.pop();
    } while (!pq.empty() && visited[curr]);
    if (visited[curr])
      break;
    visited[curr] = 1;
    for (auto &p : graph[curr]) {
      int next = p.first, d = p.second;
      if (dist[next] > dist[curr] + d) {
        dist[next] = dist[curr] + d;
        pq.push({dist[next], next});
      }
    }
  }
  return dist[e];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    int len;
    for (int i = 1; i <= n; i++)
      graph[i].clear();
    cin >> n >> m >> t >> s >> g >> h;
    while (m--) {
      int a, b, d;
      cin >> a >> b >> d;
      if ((a == g && b == h) || (a == h && b == g))
        len = d;
      graph[a].push_back({b, d});
      graph[b].push_back({a, d});
    }
    int GH = dijkstra(g, h), SG = dijkstra(s, g), SH = dijkstra(s, h);
    vector<int> ans;
    for (int i = 0; i < t; i++) {
      int x;
      cin >> x;
      int minDist = dijkstra(s, x);
      int GD = dijkstra(g, x), HD = dijkstra(h, x);
      if (SG + GH + HD == minDist || SH + GH + GD == minDist)
        ans.push_back(x);
    }
    sort(ans.begin(), ans.end());
    for (int i : ans)
      cout << i << ' ';
    cout << '\n';
  }
  return 0;
}