반응형
https://www.acmicpc.net/problem/17396
17396번: 백도어
첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는
www.acmicpc.net
[ 문제풀이 ]
1. arr 배열을 만들어서 적의 시야에 노출되어 있는지 저장합니다.
2. dijkstra를 활용하여 적의 시야에 노출되어 있지 않은 간선만을 이용해서 적의 넥서스까지 이동합니다.
3. 이동 거리가 int형을 벗어나므로 long long형으로 저장합니다.
4. 이동한 거리를 출력하고, 이동이 불가능하다면 -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 | #include<iostream> #include<vector> #include<queue> #define ll long long using namespace std; int N, M; int arr[100000]; ll visited[100000]; vector<pair<int, ll>> list[100000]; int main() { scanf("%d %d", &N, &M); for (int i = 0; i < N; i++) { scanf("%d", &arr[i]); visited[i] = 11111111111; } for (int i = 0; i < M; i++) { int a, b; ll t; scanf("%d %d %lld", &a, &b, &t); list[a].push_back({ b,t }); list[b].push_back({ a,t }); } priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.push({ 0,0 }); while (!pq.empty()) { const ll dist = pq.top().first; const int cur = pq.top().second; pq.pop(); if (cur == N - 1) { printf("%lld", dist); return 0; } if (visited[cur] < dist) continue; visited[cur] = dist; for (auto& next : list[cur]) { if ((arr[next.first] != 1 && visited[next.first] > dist + next.second) || next.first == N - 1) { visited[next.first] = next.second + dist; pq.push({ visited[next.first], next.first }); } } } printf("-1"); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 5972번 - 택배 배송 (C++) (0) | 2023.03.04 |
|---|---|
| [ 백준 ] 14284번 - 간선 이어가기 2 (C++) (0) | 2023.03.03 |
| [ 백준 ] 3066번 - 브리징 시그널 (C++) (0) | 2023.03.01 |
| [ 백준 ] 2660번 - 회장뽑기 (C++) (0) | 2023.02.28 |
| [ 백준 ] 2617번 - 구슬 찾기 (C++) (0) | 2023.02.27 |