반응형

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

 

17835번: 면접보는 승범이네

첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐

www.acmicpc.net

 

 

[ 문제풀이 ]

1. visited 배열을 만들고 visited [ i ] = 9999999999로 초기화해 줍니다.

 

2. node struct를 만들고, vector<node> list[ 100001 ]를 만들어 V, C를 저장합니다.

 

3. 각 도시에서 면접장까지 가지 않고, 반대로 면접장에서 출발할 예정이므로, U, V, C를 입력받고, list[ V ].push_back({ U, C })를 해줍니다.

 

4. 면접장이 있는 도시를 priority_queue에 넣고 dijkstra를 돌립니다.

 

5. for문을 통해 모든 도시를 돌며 거리가 가장 먼 도시를 city 변수에 저장합니다.

 

6. city와 visited[ city ]를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
#define ll long long
#define INF 9999999999
 
using namespace std;
 
struct node {
    int V;
    ll C;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.C < right.C;
    }
};
 
int N, M, K;
vector<node> list[100001];
ll visited[100001];
 
int main()
{
    priority_queue<node, vector<node>, cmp> pq;
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 1; i <= N; i++) {
        visited[i] = INF;
    }
 
    for (int i = 0; i < M; i++) {
        int U, V;
        ll C;
        scanf("%d %d %lld", &U, &V, &C);
        list[V].push_back({ U, C });
    }
 
    for (int i = 0; i < K; i++) {
        int city;
        scanf("%d", &city);
        pq.push({ city,0 });
        visited[city] = 0;
    }
 
    while (!pq.empty()) {
        const int V = pq.top().V;
        const ll C = pq.top().C;
        pq.pop();
 
        if (visited[V] < C) continue;
 
        for (auto& next : list[V]) {
            if (visited[next.V] > C + next.C) {
                visited[next.V] = C + next.C;
                pq.push({ next.V, C + next.C });
            }
        }
    }
 
    int city = 0;
    ll ans = 0;
 
    for (int i = 1; i <= N; i++) {
        if (ans < visited[i]) {
            city = i;
            ans = visited[i];
        }
    }
 
    printf("%d\n%lld", city, ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2458번 - 키 순서 (C++)  (0) 2023.02.07
[ 백준 ] 2211번 - 네트워크 복구 (C++)  (0) 2023.02.06
[ 백준 ] 1368번 - 물대기 (C++)  (0) 2023.02.04
[ 백준 ] 1261번 - 알고스팟 (C++)  (0) 2023.02.03
[ 백준 ] 10423번 - 전기가 부족 (C++)  (0) 2023.02.02

+ Recent posts

티스토리툴바