백준 민준이와 마산 그리고 건우

작성일 | In |

Problem : 민준이와 마산 그리고 건우

유형 : 다익스트라

문제 해석

  • 민준이가 건우를 도울 수 있는지 확인하라

문제 재해석

  • 민준이가 건우를 들려서 가는 경우에도 최단거리가 유지되는지 확인하라.
  • 양방향 간선이다.
  • 출발지에서 목적지 까지 가는 간선은 항상 존재한다.
  • 출발지에서 건우에게 가는 간선은 항상 존재한다.

해결 전략

  • 시작점에서 건우까지 가는 비용 + 건우에서 목적지까지 가는 비용
  • 시작점에서 목적지까지 바로 가는 비용
  • :heavy_check_mark: 이 두가지가 같은지 확인한다.

주의할 점

  • 최단 경로가 여러개 일 수 있다.
  • :x: 최단 경로를 구한 뒤 경로 역추적을 통하는 방법으로는 올바른 답을 구할 수 없다.
  • 건우위치에서 마산까지 가는 경로는 보장되지 않는다. (예외 처리 필요)

코드

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
87
 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

int MaSan, e, GunWoo;

int INF = INT_MAX;
int cost[5002];

vector<pii> node[5002];

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

int Dijkstra(int st, int ed) {
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    Init();

    cost[st] = 0;
    pq.push({ 0,st });

    while (!pq.empty()) {
        auto cur = pq.top();    pq.pop();
        int cur_cost = cur.first;
        int cur_spot = cur.second;

        if (cur_cost != cost[cur_spot]) continue;
        if (cur_spot == ed) return cur_cost;

        for (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 -1;
}


int Visit_GunWoo() {
    int GunWoo_cost1 = Dijkstra(1, GunWoo);
    if (GunWoo_cost1 == -1) return -1;
    
    int GunWoo_cost2 = Dijkstra(GunWoo, MaSan);
    if (GunWoo_cost2 == -1) return -1;

    return GunWoo_cost1 + GunWoo_cost2;
}

int Go_MaSan() {
    return Dijkstra(1, MaSan);
}

void Solve() {
    if (Visit_GunWoo() == Go_MaSan()) cout << "SAVE HIM\n";
    else cout << "GOOD BYE\n";
}

void Input() {
    cin >> MaSan >> e >> GunWoo;

    int a, b, _cost;
    for (int i = 0; i < e; ++i) {
        cin >> a >> b >> _cost;
        node[a].push_back({ _cost, b });
        node[b].push_back({ _cost, a });
    }
}

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

    Input();
    Solve();

    return 0;
}

피드백

  • 입력의 순서를 조심하자.