BOJ 1504 - 특정한 최단 경로

📌 문제 출처: BOJ 1504 - 특정한 최단 경로

---

제목

( 7/28 - class4 : 백준1504 )

---

문제 유형

• 최단 경로
• Dijkstra (다익스트라)

---

풀이 방법 도출

• 다익스트라 3회 실행: 시작점(1), 경유지(v1), 경유지(v2)에서
• 두 가지 경로 고려:
  • 1 → v1 → v2 → N
  • 1 → v2 → v1 → N
• 두 경로 중 가능한 최소값을 선택

---

시간 복잡도

• 다익스트라 3회: O((E + V) log V)
• V ≤ 800, E ≤ 200,000이므로 충분히 통과 가능

---

코드

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

#define X first
#define Y second

using ll = long long;

int n, e;
vector<pair<int,int>> adj[805];
const int INF = 1e9+10;
int v1, v2;

vector<int> dijkstra(int start) {
  priority_queue<pair<int,int>,
    vector<pair<int,int>>,
    greater<pair<int,int>> > pq;

  vector<int> dist(n+1, INF);

  dist[start] = 0;
  pq.push({dist[start], start});

  while(!pq.empty()) {
    auto cur = pq.top(); pq.pop();
    if(dist[cur.Y] != cur.X) continue;
    for(auto nxt : adj[cur.Y]) {
      if(dist[nxt.Y] <= dist[cur.Y] + nxt.X) continue;
      dist[nxt.Y] = dist[cur.Y] + nxt.X;
      pq.push({dist[nxt.Y], nxt.Y});
    }
  }

  return dist;
}


int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> e;

  while(e--) {
    int a, b, c;
    cin >> a >> b >> c;
    adj[a].push_back({c, b});
    adj[b].push_back({c, a});
  }

  cin >> v1 >> v2;

  auto d_from_1 = dijkstra(1);
  auto d_from_v1 = dijkstra(v1);
  auto d_from_v2 = dijkstra(v2);

  ll path1 = 1LL*d_from_1[v1] + d_from_v1[v2] + d_from_v2[n];
  ll path2 = 1LL*d_from_1[v2] + d_from_v2[v1] + d_from_v1[n];

  ll ans = min(path1, path2);
  if(ans >= INF) cout << -1;
  else cout << ans;
}