Easy is Perfect

[백준] 1504번 C/C++ 풀이 _ 특정한 최단 경로

  • melonicedlatte
  • Aug 19, 2018


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

특정한 최단 경로 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB106402629166722.185%

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2<=N<=800, 0<=E<=200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1<=c<=1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호가 주어진다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제 입력 1 

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1 

7

출처

알고리즘 분류

풀이


위의 문제는 양의 간선만 나오기 때문에 '다익스트라' 문제인 것을 짐작할 수 있지만, 특이한 조건이 있습니다. 
두 개의 '필수적으로 지나야 하는 노드' 가 주어집니다. 

두 개의 노드를 각각 a, b 라고 해보겠습니다. 
위의 그림과 같이 a, b를 모두 지나면서 1에서 출발하여 N으로 가는 경로는 1번 경로와 2번 경로로 2가지가 존재합니다. 

따라서, 1번의 경로에 해당하는 다익스트라 3가지, 2번의 경로에 해당하는 다익스트라 3가지를 각각 구해주어야 합니다. 

ex ) 1->a->b->N 일 경우에는 1의 다익스트라, a의 다익스트라, b의 다익스트라가 필요 

다익스트라의 시간 복잡도는 O(ElogE) 정도이기 때문에, 6번 정도의 다익스트라를 수행한다고 해도 시간 초과는 발생하지 않습니다. 

함수를 효율적으로 만들어서 3번 정도만 다익스트라 함수를 호출해도 되지만,
시간 초과가 발생하지 않아서 저는 그냥 원하는 도착지의 값만 출력했습니다. 

소스코드

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
88
89
90
91
92
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;  
 
#define INF 987654321
int N, E;
vector<map<int, int>> edge_vec;
 
int dijkstra(int _start, int _end) { 
    vector<int> distance(N + 1, INF); 
    priority_queue<int, vector<int>, greater<int> > pq;
 
    distance.at(_start) = 0;
 
    // 다익스트라 진행 
    pq.push(_start);
    while (!pq.empty()) {
        // 현재 노드에서 엣지를 탐색한 다음에 값들 갱신 
        int now_node_ = pq.top();  pq.pop(); 
 
        // 엣지들을 탐색하면서 거리 값을 갱신한다. 
        for (auto edge_ : edge_vec.at(now_node_)) {
            int to_ = edge_.first;
            int weight_ = edge_.second;
 
            // 거리가 작으면 값을 갱신 
            if (weight_ + distance.at(now_node_) < distance.at(to_)) {
                distance.at(to_) = weight_ + distance.at(now_node_);
                pq.push(to_);
            }
        }
    }
 
    return distance.at(_end);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin >> N >> E;
    edge_vec.resize(N+1);
 
    // 엣지 연결
    for (int e_idx = 0; e_idx < E; e_idx++) {
        int node_1_, node_2_, weight_;
        cin >> node_1_ >> node_2_ >> weight_;
 
        // 값이 존재 한다면 더 적은 값으로 교체
        if (edge_vec.at(node_1_)[node_2_] == 0)
            edge_vec.at(node_1_)[node_2_] = weight_;
        else if (weight_ < edge_vec.at(node_1_)[node_2_])
            edge_vec.at(node_1_)[node_2_] = weight_;
 
        if (edge_vec.at(node_2_)[node_1_] == 0)
            edge_vec.at(node_2_)[node_1_] = weight_;
        else if (weight_ < edge_vec.at(node_2_)[node_1_])
            edge_vec.at(node_2_)[node_1_] = weight_;
    }
 
    int start = 1, end = N;
    int a, b;
    cin >> a>> b;
     
    // start -> a -> b -> N
    int start_a = dijkstra(start, a);
    int a_b = dijkstra(a, b);
    int b_N = dijkstra(b, N);
    int is_possible_1 = 0 ;
 
    // 가능여부 체크
    if (start_a == INF || a_b == INF || b_N == INF) is_possible_1 = 0; 
    else is_possible_1 = 1;
 
    // start -> b -> a -> N
    int start_b = dijkstra(start, b);
    int b_a = dijkstra(b, a);
    int a_N = dijkstra(a, N);
    int is_possible_2 = 0;
 
    // 가능여부 체크
    if (start_b == INF || b_a == INF || a_N == INF) is_possible_2 = 0;
    else is_possible_2 = 1;
 
    if (is_possible_1 == 0 && is_possible_2 == 0) cout << "-1";
    else 
        cout << min({ start_a + a_b + b_N , start_b + b_a + a_N });
 
    return 0; 
}
cs



Search