반응형

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

 

9370번: 미확인 도착지

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. s, g, h 노드에서 각각의 다익스트라를 구현하여 각각의 노드에서의 최단거리를 저장합니다.

 

2. s -> g -> h -> t 까지의 거리와 s -> t 까지의 거리가 같거나 s -> h -> g -> t 까지의 거리와 s -> t 까지의 거리가 같으면 t를 출력합니다.

 

[ 소스코드 ]

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct node {
    int to;
    int dist;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.dist < right.dist;
    }
};
 
vector<pair<int, int>> list[2001];
 
int n, m, t;
int s, g, h;
int visiteds[2001];
int visitedg[2001];
int visitedh[2001];
int des[100];
int dist;
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int tc = 0; tc < T; tc++) {
 
        priority_queue<node, vector<node>, cmp> pq;
 
        scanf("%d %d %d", &n, &m, &t);
        scanf("%d %d %d", &s, &g, &h);
 
        for (int i = 1; i <= n; i++) {
            visiteds[i] = 987654321;
            visitedg[i] = 987654321;
            visitedh[i] = 987654321;
            list[i].clear();
        }
 
        for (int i = 0; i < m; i++) {
            int a, b, d;
            scanf("%d %d %d", &a, &b, &d);
 
            list[a].push_back({ b,d });
            list[b].push_back({ a,d });
        }
 
        for (int i = 0; i < t; i++) {
            scanf("%d", &des[i]);
        }
 
        sort(des, des + t);
 
        pq.push({ s,0 });
 
        while (!pq.empty()) {
            const int cur = pq.top().to;
            const int dist = pq.top().dist;
            pq.pop();
 
            if (visiteds[cur] < dist) continue;
            visiteds[cur] = dist;
 
            for (auto& next : list[cur]) {
                const int nextNode = next.first;
                const int nextDist = next.second;
 
                if (visiteds[nextNode] > nextDist + dist) {
                    visiteds[nextNode] = nextDist + dist;
                    pq.push({ nextNode,nextDist + dist });
                }
            }
        }
 
        pq.push({ g,0 });
 
        while (!pq.empty()) {
            const int cur = pq.top().to;
            const int dist = pq.top().dist;
            pq.pop();
 
            if (visitedg[cur] < dist) continue;
            visitedg[cur] = dist;
 
            for (auto& next : list[cur]) {
                const int nextNode = next.first;
                const int nextDist = next.second;
 
                if (visitedg[nextNode] > nextDist + dist) {
                    visitedg[nextNode] = nextDist + dist;
                    pq.push({ nextNode,nextDist + dist });
                }
            }
        }
 
        pq.push({ h,0 });
 
        while (!pq.empty()) {
            const int cur = pq.top().to;
            const int dist = pq.top().dist;
            pq.pop();
 
            if (visitedh[cur] < dist) continue;
            visitedh[cur] = dist;
 
            for (auto& next : list[cur]) {
                const int nextNode = next.first;
                const int nextDist = next.second;
 
                if (visitedh[nextNode] > nextDist + dist) {
                    visitedh[nextNode] = nextDist + dist;
                    pq.push({ nextNode,nextDist + dist });
                }
            }
        }
 
        for (int i = 0; i < t; i++) {
            if ((visiteds[g] + visitedg[h] + visitedh[des[i]] == visiteds[des[i]]) || (visiteds[h] + visitedh[g] + visitedg[des[i]] == visiteds[des[i]])) {
                printf("%d ", des[i]);
            }
        }
 
        printf("\n");
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 10836번 - 여왕벌 (C++)  (0) 2023.04.28
[ 백준 ] 2513번 - 통학버스 (C++)  (0) 2023.04.27
[ 백준 ] 2671번 - 잠수함식별 (C++)  (0) 2023.04.25
[ 백준 ] 17218번 - 비밀번호 만들기 (C++)  (0) 2023.04.24
[ 백준 ] 6987번 - 월드컵 (C++)  (0) 2023.04.23

+ Recent posts

티스토리툴바