백준 1504 특정한 최단 경로

작성일 | In |

Problem : 특정한 최단 경로

유형 : 다익스트라

문제 해석

  • 반드시 들려야 하는 정점들을 거치며 목적지까지 가는 최단 거리를 구하라.

문제 재해석

  • 반드시 들려야 하는 정점은 두 개 이다.
  • 경로가 없을 경우 -1 를 출력한다.

해결 전략

  • 들려야 하는 정점은 2개밖에 없다.
  • 즉, 경우의 수는 2! 밖에 나오지 않는다.
  • 다익스트라로 전부 진행해본다.
  • 해봐야 6 * ElogE 이기 때문에 전부 해보면 된다.

주의할 점

  • INT_MAX 가 더해지며 오버플로우 나는것을 주의한다.
  • 최대 3번 까지 더해질 수 있다. 모두 경로가 없는 경우

설계, 구현

  • v1를 먼저 들리는 경우
  • v2를 먼저 들리는 경우
  • 두 가지를 전부 진행 해본다.
  • 두 가지 경로의 결과 값이 INF 보다 크다면 -1 을 출력한다.
  • 그렇지 않다면, 둘 중 작은 값을 출력한다.

코드

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;

const int INF = INT_MAX;
vector<pii> node[802];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int cost[802];

int n, m;
int v1, v2;

void Reset() {
    for (int i = 1; i <= n; ++i) {
        cost[i] = INF;
    }
}

ll Dijstra(int st, int fin) {
    Reset();
    pq.push({ 0,st });
    cost[st] = 0;

    while (!pq.empty()) {
        auto cur = pq.top();    pq.pop();

        int cur_cost = cur.first;
        int cur_spot = cur.second;
        if (cost[cur_spot] != cur_cost) continue;

        for (const auto &nxt : node[cur_spot]) {
            int nxt_cost = cur_cost + nxt.first;
            int nxt_spot = nxt.second;

            if (nxt_cost < cost[nxt_spot]) {
                cost[nxt_spot] = nxt_cost;
                pq.push({ nxt_cost, nxt_spot });
            }
        }
    }
    return (ll)cost[fin];
}

ll Visit_v1_First() {
    return Dijstra(1, v1) + Dijstra(v1, v2) + Dijstra(v2, n);
}

ll Visit_v2_First() {
    return Dijstra(1, v2) + Dijstra(v2, v1) + Dijstra(v1, n);
}

void Solve() {
    ll route1 = Visit_v1_First();
    ll route2 = Visit_v2_First();

    if (route1 >= INF and route2 >= INF) {
        cout << -1 << "\n";
    }
    else cout << min(route1, route2) << "\n";
}


void Input() {
    cin >> n >> m;

    int a, b, _cost;
    while (m--) {
        cin >> a >> b >> _cost;
        node[a].push_back({ _cost, b });
        node[b].push_back({ _cost, a });
    }
    cin >> v1 >> v2;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • 다익스트라 짜는 속도를 좀 더 올리자.