|
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
|
#include <bits/stdc++.h>
using namespace std;
int N, M, K;
int num;
int res;
int ju[101];
int visited[101][1 << 16];
typedef pair<int, int> pii;
vector<vector<pii>>graph;
typedef struct info {
int cur, state, cnt;
};
void solve()
{
queue<info>q;
q.push({ 1,0,0 });
visited[1][0] = 1;
while (!q.empty())
{
int cur = q.front().cur;
int state = q.front().state;
int cnt = q.front().cnt;
q.pop();
if (cur == 1)
{
int n_cnt = cnt;
if (ju[1]&&cnt<14&&!(state&(1<<1)))
n_cnt++;
res = max(res, n_cnt);
}
for (auto next : graph[cur])
{
int _next = next.first;
int limit = next.second;
int ju_chk = ju[_next];
if (ju_chk)
{
int n_state = state | (1 << ju_chk);
if (cnt + 1 <= limit && !visited[_next][n_state]&& !(state & (1 << ju_chk)))
{
visited[_next][n_state] = 1;
q.push({ _next,n_state,cnt + 1 });
}
}
if (cnt > limit || visited[_next][state])continue;
visited[_next][state] = 1;
q.push({ _next,state,cnt });
}
}
cout << res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int i, j;
cin >> N >> M >> K;
for (i = 1; i <=K; i++)
{
cin >> num;
ju[num] = i;
}
int a, b, c;
graph.resize(N + 1);
for (i = 0; i < M; i++)
{
cin >> a >> b >> c;
graph[a].push_back({ b,c });
graph[b].push_back({ a,c });
}
solve();
}
|
cs |
bfs + 비트마스킹
보석 14개니까 visited[섬의 최대 갯수][1<<16개]로 선언하였음
1번이 보석 가지고 있을경우 27번처럼
int n_cnt = cnt;
if (ju[1]&&cnt<14&&!(state&(1<<1)))
n_cnt++;
해도되고
그냥 처음에 graph[1].push_back({1,15}); 해도됨 왜냐면
어차피 1로 돌아왔을땐 다리를 건넌거니 1번에있는 보석은 그냥 추가해도되니까
근데 위에거가 속도살짝 빠름
'백준 알고리즘' 카테고리의 다른 글
| [C++] 백준알고리즘 2529번 부등호 문제 (0) | 2020.05.06 |
|---|---|
| [C++] 백준알고리즘 5430번 AC문제 (0) | 2020.04.24 |
| [C++] 백준알고리즘 2661번 좋은수열 문제 (0) | 2020.04.24 |
| [C++] 백준알고리즘 2485번 가로수 문제 (0) | 2020.04.24 |
| [C++] 백준알고리즘 1644번 소수의 연속합 문제 (0) | 2020.03.13 |