BOJ 1504: 특정한 최단 경로

작성일

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

  • 2월동안 187문제 풀기(지난달 누적 87개) (62/187)
  • 다익스트라 여러번쓰기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

struct Node { int p, cost; };
auto cmp = [](Node a, Node b) { return a.cost > b.cost; };

struct Edge { int p, cost; };
vector<Edge> adj[801];
int N, E, A, B;

void fillInput() {
  ios::sync_with_stdio(false);
  cin >> N >> E;
  for(int i = 0; i < E; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    u--, v--;
    adj[u].push_back({v, c});
    adj[v].push_back({u, c});
  }
  cin >> A >> B;
  A--, B--;
}

void shortestPath(int s, vector<int>& cost) {
  cost.assign(N, 1e9);
  priority_queue<Node,vector<Node>,decltype(cmp)> pq(cmp);
  pq.push({s,0});
  cost[s] = 0;

  while(pq.size()) {
    Node cur = pq.top();
    pq.pop();
    if(cur.cost != cost[cur.p]) continue;

    for (Edge& e : adj[cur.p]) {
      if(cost[e.p] > e.cost + cur.cost) {
        cost[e.p] = e.cost + cur.cost;
        pq.push({e.p, cost[e.p]});
      }
    }
  }
}

int main() {
  fillInput();
  vector<int> cost;
  shortestPath(0, cost);
  long long z2A = cost[A];
  long long z2B = cost[B];
  shortestPath(A, cost);
  long long A2N = cost[N-1];
  long long A2B = cost[B];
  shortestPath(B, cost);
  long long B2N = cost[N-1];
  long long B2A = cost[A];

  long long dist = min(z2A+A2B+B2N, z2B+B2A+A2N);
  cout << (dist >= 1e9 ? -1 : dist);
}