[백준 / BOJ] C++ 1185 유럽여행

1185번: 유럽여행

 

문제

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

1185번: 유럽여행

 

 

풀이

모든 나라를 방문해야 하고 길은 N-1개만 남겨야 하므로 최소 스패닝 트리(MST) 알고리즘을 사용한다. 보통 최소 스패닝 트리 문제는 간선의 가중치가 이동 거리, 시간, 비용 등인데 이 문제에서는 방문한 나라에 도착한 시점에 내는 비용도 고려해야 한다. 따라서 도착한 지점의 비용을 어떻게 처리할 것인지가 문제를 푸는 핵심이다.

 

먼저 N번 나라에서 출발했으면 마지막에 N번 나라로 돌아와야 하기 때문에 모든 간선은 2번 지나가게 된다. 그리고 A나라에서 B나라로 이어지고 B나라에서 C나라로 이어지는 경우 A나라의 방문 비용은 1번, B나라는 2번, C나라는 1번이다. 이 말은 각 간선이 연결될 때마다 출발 지점과 도착 지점의 도시 비용을 추가해줘야 한다는 것이고 다시 말해, 간선의 최소 비용을 고려할 때 출발 지점과 도착 지점의 비용을 함께 고려해야 한다는 말이다. 따라서 우리는 간선을 입력받을 때 {간선을 통과하는 비용 × 2 + 출발 지점의 방문 비용 + 도착 지점의 방문 비용}을 가중치로 생각하고 최소 스패닝 트리(MST)의 가중치를 구해야 한다.

 

그리고 출발 지점에 상관없이 모든 나라를 이동하는 비용은 같으므로 각 나라 중 방문 비용이 가장 싼 나라부터 시작하면 된다. 즉, 최소 스패닝 트리(MST)의 가중치를 구할 때 초기값을 0이 아닌 가장 싼 방문 비용으로 하면 된다.

 

 

코드

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

int N, P;
vector<pair<int, pair<int, int>>> edge;
vector<int> p;

int find(int x) {
  if (p[x] != x)
    p[x] = find(p[x]);
  return p[x];
}

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if (x < y)
    p[y] = x;
  else
    p[x] = y;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N >> P;
  p.resize(N + 1);
  iota(p.begin(), p.end(), 0);
  vector<int> c(N + 1);
  for (int i = 1; i <= N; i++)
    cin >> c[i];
  while (P--) {
    int S, E, L;
    cin >> S >> E >> L;
    edge.push_back({2 * L + c[S] + c[E], {S, E}});
  }
  sort(edge.begin(), edge.end());
  int ans = *min_element(c.begin() + 1, c.end());
  for (auto [weight, path] : edge)
    if (find(path.first) != find(path.second)) {
      ans += weight;
      merge(path.first, path.second);
    }
  cout << ans;
  return 0;
}