문제 URL : https://www.acmicpc.net/problem/11952
11952번: 좀비
첫 번째 줄에 N, M, K, S가 공백으로 구분되어 입력된다. 각 값은 도시의 수, 길의 수, 좀비에게 점령당한 도시의 수, 위험한 도시의 범위 를 의미한다. (2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2,
www.acmicpc.net
문제 접근법 :
쉽게설명하자면
BFS + 다익스트라 문제입니다.
좀비에게 점령당한 도시로부터 거리가 s이하 만큼 떨어진 도시들을 구하는것은 BFS를 이용합니다.
그렇다면 예제 1번의 그림은
이런식으로 하늘색으로 칠해진 도시는 위험한도시이고 하얀색은 안전도시이며, 검은색은 좀비에게 점령당한도시입니다.
자 그럼여기서 각노드들의 가중치가 계산될수있는데
안전한도시는 p원 위험한도시는 q원이니
그것을 그대로 그려보면
이와같은 그림이나온다 따라서 1번부터 싲가해서 13번까지 도달하게되면 11000원이 나오게됩니다.
소스코드 :
|
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
|
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m, k, s;
ll p, q;
vector<ll> city,dead,v[100001];
void input() {
cin >> n >> m >> k >> s;
cin >> p >> q;
city = vector<ll>(n + 1);
for (ll i = 0; i < k; i++) {
ll a;
cin >> a;
dead.push_back(a);
}
for (ll i = 0; i < m; i++) {
ll a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
}
void bfs() {
queue<ll> q;
for (ll t : dead) {
q.push(t);
city[t] = 2;//점령 당한도시
}
ll h = 0;
while (!q.empty()) {
int qsize = q.size();
while (qsize--) {
ll cur = q.front();
q.pop();
for (ll next : v[cur]) {
if (city[next] == 0) {
city[next] = 1;
q.push(next);
}
}
}
h++;
if (h >= s)break;
}
}
ll dijkstrak() {
priority_queue<pair<ll, ll>> pq;
pq.push({ 0,1 });
vector<ll> dist(n + 1, 1e14);
dist[1] = 0;
while (!pq.empty()) {
ll sumcost, cur;
sumcost = -pq.top().first;
cur = pq.top().second;
pq.pop();
if (dist[cur] < sumcost)continue;
for (ll next : v[cur]) {
ll cost = sumcost;
if (city[next])
cost += q;
else
cost += p;
if (dist[next] > cost&&city[next]!=2) {
dist[next] = cost;
pq.push({ -cost,next });
}
}
}
return dist[n] - (city[n] ? q : p);
}
void solve() {
bfs();
cout << dijkstrak() << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 21611 마법사 상어와 블리자드 (0) | 2022.07.21 |
|---|---|
| 백준 16681 등산 (0) | 2022.07.13 |
| 백준 14461 소가 길을 건너간 이유 7 (0) | 2022.07.13 |
| 백준 12852 1로 만들기 2 (0) | 2022.07.13 |
| 백준 16637 괄호 추가하기 (0) | 2022.05.17 |
