반응형

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

 

20168번: 골목 대장 호석 - 기능성

첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 교차차로를 입력받아 vector list에 저장하고, visited[ cost ][ node ]를 만들어 지나온 길 중 가장 큰 비용이 cost이고, 해당 node에 도착했을 때 총비용을 저장합니다.

 

2. bfs를 통해 A부터 노드들을 돌면서 B에 도착했을 때 cost의 최솟값을 ans에 저장합니다.

 

3. ans의 값이 987654321이라면 -1을, 그렇지 않다면 ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
struct node {
    int cur;
    int cost;
    int shame;
};
 
int N, M, A, B, C;
int visited[1001][11];
vector<pair<int,int>> list[11];
int ans = 987654321;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> A >> B >> C;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= 1000; j++) {
            visited[j][i] = 987654321;
        }
    }
    
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
 
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    queue<node> q;
 
    q.push({ A,0,0 });
 
    while (!q.empty()) {
        const int cur = q.front().cur;
        const int cost = q.front().cost;
        const int shame = q.front().shame;
        q.pop();
 
        if (cur == B) {
            ans = min(ans, shame);
            continue;
        }
 
        if (visited[shame][cur] < cost) continue;
        visited[shame][cur] = cost;
 
        for (auto& next : list[cur]) {
            int Max = max(shame, next.second);
            if (visited[Max][next.first] > cost + next.second && cost + next.second <= C) {
                visited[Max][next.first] = cost + next.second;
                q.push({ next.first,cost + next.second, Max });
            }
        }
    }
 
    if (ans == 987654321) cout << -1;
    else cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2224번 - 명제 증명 (C++)  (0) 2023.08.15
[ 백준 ] 20182번 - 골목 대장 호석 - 효율성 1 (C++)  (0) 2023.08.14
[ 백준 ] 16472번 - 고냥이 (C++)  (0) 2023.08.12
[ 백준 ] 9024번 - 두 수의 합 (C++)  (0) 2023.08.11
[ 백준 ] 3079번 - 입국심사 (C++)  (0) 2023.08.10

+ Recent posts

티스토리툴바