반응형

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

 

20183번: 골목 대장 호석 - 효율성 2

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 그래프를 입력받고, vector<pair<int, int>> list[ 100001 ] 배열에 저장합니다. 

 

2. 매개 변수를 활용하여 이동할 수 있는 골목의 최대 비용을 정해서 dijkstra를 돌립니다.

 

3. ans를 -1로 초기화하고, 만약 도착지에 도착하게 되면 ans에 해당 매개 변수 값을 저장합니다.

 

4. 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
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<queue>
#include<vector>
#define ll long long
 
using namespace std;
 
int N, M;
int A, B;
ll C;
vector<pair<int, int>> list[100001];
int s, e;
int ans = -1;
ll visited[100001];
 
bool dijkstra(int m)
{
    fill(visited, visited + N + 1, 111111111111111);
    priority_queue<pair<ll, int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
 
    pq.push({ 0,A });
 
    while (!pq.empty()) {
        const ll cost = pq.top().first;
        const int cur = pq.top().second;
        pq.pop();
 
        if (cost > C) continue;
 
        if (cur == B) {
            return true;
        }
 
        if (visited[cur] < cost) continue;
        visited[cur] = cost;
 
        for (auto& next : list[cur]) {
            if (visited[next.second] > cost + next.first && next.first <= m) {
                visited[next.second] = cost + next.first;
                pq.push({ cost + next.first, next.second });
            }
        }
    }
 
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> A >> B >> C;
    s = 1;
 
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        list[u].push_back({ w,v });
        list[v].push_back({ w,u });
        e = max(e, w);
    }
 
    while (s <= e) {
        int m = (s + e) / 2;
 
        if (dijkstra(m)) {
            ans = m;
            e = m - 1;
        }
        else {
            s = m + 1;
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5569번 - 출근 경로 (C++)  (0) 2023.09.18
[ 백준 ] 13398번 - 연속합 2 (C++)  (0) 2023.09.17
[ 백준 ] 5549번 - 행성 탐사 (C++)  (0) 2023.09.15
[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
반응형

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

 

20160번: 야쿠르트 아줌마 야쿠르트 주세요

첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 그래프를 입력받고, vector<pair<int, int>> list[ 10001 ] 배열에 저장합니다. 

 

2. dijkstra를 이용하여 야쿠르트 아줌마의 정점별 도착 거리를 구해 저장합니다.

 

3. dijkstra를 이용하여 나의 정점별 도착 거리를 visited 배열에 저장하고, for문을 통해 돌면서 아줌마의 도착 시점보다 내 도착 시점이 빠르거나 같은 지점을 ans에 저장합니다.

 

4. 만약 어느 정점에도 도착할 수 없다면 -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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<queue>
#include<vector>
#define ll long long
 
using namespace std;
 
int V, E;
vector<pair<int, int>> list[10001];
int arr[10];
ll dist[10];
int start;
ll visited[10001];
 
int dijkstra(int s, int e)
{
    fill(visited, visited + V + 1, 11111111111);
    visited[s] = 0;
 
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
 
    pq.push({ 0,s });
 
    while (!pq.empty()) {
        const int cur = pq.top().second;
        const int dist = pq.top().first;
        pq.pop();
 
        if (cur == e) {
            return dist;
        }
 
        if (visited[cur] < dist) continue;
        visited[cur] = dist;
 
        for (auto& next : list[cur]) {
            if (visited[next.second] > dist + next.first) {
                visited[next.second] = dist + next.first;
                pq.push({ visited[next.second], next.second });
            }
        }
    }
 
    return -1;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> V >> E;
 
    for (int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        list[u].push_back({ w,v });
        list[v].push_back({ w,u });
    }
 
    for (int i = 0; i < 10; i++) {
        cin >> arr[i];
    }
 
    cin >> start;
 
    int cnt = 1;
 
    for (int i = 0; i < 9; i++) {
        int next = dijkstra(arr[i], arr[i + cnt]);
        while (next == -1) {
            dist[i + cnt] = -1;
            cnt++;
            if (i + cnt == 10) break;
            next = dijkstra(arr[i], arr[i + cnt]);
        }
        if (i + cnt == 10) break;
        dist[i + cnt] = dist[i] + dijkstra(arr[i], arr[i + cnt]);
        i = i + cnt - 1;
        cnt = 1;
    }
 
    dijkstra(start, 0);
    int ans = 111111;
 
    for (int i = 0; i < 10; i++) {
        if (visited[arr[i]] <= dist[i]) {
            ans = min(ans, arr[i]);
        }
    }
 
    if (ans == 111111) cout << -1;
    else cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20183번 - 골목 대장 호석 - 효율성 2 (C++)  (0) 2023.09.16
[ 백준 ] 5549번 - 행성 탐사 (C++)  (0) 2023.09.15
[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
[ 백준 ] 22116번 - 창영이와 퇴근 (C++)  (0) 2023.09.12
[ 백준 ] 3755번 - Double Queue (C++)  (0) 2023.09.11
반응형

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

 

22116번: 창영이와 퇴근

A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 격자를 입력받고, arr 배열에 저장합니다.

 

2. visited 배열을 만들어 해당 구간에 도착했을 때 경사로 차가 가장 적었을 때의 값을 저장합니다.

 

3. ans에 경사로 차 중 가장 큰 값을 저장합니다.

 

4. 다익스트라를 이용하여 경사로의 높이차가 작은 구간부터 방문하고, N - 1, N - 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
70
71
#include<iostream>
#include<queue>
#include<cmath>
 
using namespace std;
 
struct node {
    int y, x, h;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.h < right.h;
    }
};
 
int N;
int arr[1000][1000];
int visited[1000][1000];
int ans;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
            visited[i][j] = 1111111111;
        }
    }
 
    priority_queue<node, vector<node>, cmp> pq;
    pq.push({ 0,0,0 });
    visited[0][0] = 0;
 
    while (!pq.empty()) {
        const int y = pq.top().y;
        const int x = pq.top().x;
        const int h = pq.top().h;
        pq.pop();
 
        if (visited[y][x] < h) continue;
 
        ans = max(ans, h);
 
        if (y == N - 1 && x == N - 1) {
            cout << ans;
            return 0;
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                int diff = abs(arr[y][x] - arr[yy][xx]);
                if (visited[yy][xx] > diff) {
                    visited[yy][xx] = diff;
                    pq.push({ yy,xx,diff });
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
[ 백준 ] 3755번 - Double Queue (C++)  (0) 2023.09.11
[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
반응형

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

 

1486번: 등산

첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/24

 

[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk

rudalsd.tistory.com

 

 

1. 지도를 입력받고, arr 배열에 높이를 저장합니다.

 

2. 각 좌표에 번호를 달고 플로이드 와샬 알고리즘을 통해 floyd[ N * M ][ N * M ] 배열에 번호별로 이동거리를 저장합니다.

 

3. floyd[ 0 ][ i ] + floyd[ i ][ 0 ]의 값이 D보다 작은 번호들 중 좌표의 높이값이 가장 큰 값을 ans에 저장합니다.

 

4. 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
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<string>
#include<cmath>
 
using namespace std;
 
int N, M, T, D;
int arr[25][25];
int floyd[625][625];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> T >> D;
 
    for (int i = 0; i < N; i++) {
        string temp;
        cin >> temp;
 
        for (int j = 0; j < M; j++) {
            if (temp[j] >= 'a') {
                arr[i][j] = temp[j] - 'a' + 26;
            }
            else {
                arr[i][j] = temp[j] - 'A';
            }
        }
    }
 
    for (int i = 0; i < N * M; i++) {
        for (int j = 0; j < N * M; j++) {
            floyd[i][j] = -1;
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            for (int k = 0; k < 4; k++) {
                int yy = i + dy[k];
                int xx = j + dx[k];
 
                if (yy >= 0 && yy < N && xx >= 0 && xx < M && abs(arr[yy][xx] - arr[i][j]) <= T) {
                    if (arr[i][j] < arr[yy][xx]) {
                        floyd[M * i + j][M * yy + xx] = (arr[yy][xx] - arr[i][j]) * (arr[yy][xx] - arr[i][j]);
                    }
                    else {
                        floyd[M * i + j][M * yy + xx] = 1;
                    }
                }
            }
        }
    }
 
    for (int i = 0; i < N * M; i++) {
        for (int j = 0; j < N * M; j++) {
            for (int k = 0; k < N * M; k++) {
                if (j!=k && floyd[j][i] != -1 && floyd[i][k] != -1) {
                    if (floyd[j][k] == -1 || floyd[j][k] > floyd[j][i] + floyd[i][k]) {
                        floyd[j][k] = floyd[j][i] + floyd[i][k];
                    }
                }
            }
        }
    }
 
    int ans = arr[0][0];
 
    for (int i = 1; i < N * M; i++) {
        if (floyd[0][i] != -1 && floyd[i][0] != -1 && floyd[i][0] + floyd[0][i] <= D) {
            ans = max(ans, arr[i / M][i % M]);
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04
[ 백준 ] 7299번 - Food Cubes (C++)  (0) 2023.09.02
[ 백준 ] 1339번 - 단어 수학 (C++)  (0) 2023.09.01
[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31
반응형

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

 

20007번: 떡 돌리기

첫째줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N) 두번째 줄부터 M+1번째 줄까지 A와 B 그리고 A집과 B집 사이의 도로의 길이 C가 주

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 이어진 집들을 입력받고, vector<pair<int, int>> list[ 1000 ]에 저장하고, visited[ 1000 ] 배열을 만들어 거리를 저장합니다.

 

2. 데이크스트라를 이용하여, Y부터 각 집까지의 거리를 visited 배열에 저장합니다.

 

3. visited 배열을 오름차순으로 정렬하고, for문을 통해 돌면서 거리 * 2의 값을 더해주면서 X를 넘으면 ans++를 해줍니다.

 

4. 이때, 거리 * 2의 값이 X보다 크다면 -1을 출력하고, 그렇지 않다면 ans + 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
using namespace std;
 
int N, M, X, Y;
vector<pair<int, int>> list[1000];
int visited[1000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> X >> Y;
 
    fill(visited, visited + N, -1);
 
    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 });
    }
 
    priority_queue<pair<int, int>> pq;
 
    pq.push({ 0,Y });
 
    while (!pq.empty()) {
        const int cur = pq.top().second;
        const int cost = pq.top().first;
        pq.pop();
 
        if (visited[cur] == -1 || visited[cur] >= cost) {
            visited[cur] = cost;
        }
 
        for (auto& next : list[cur]) {
            int nextCost = next.second;
            int nextNode = next.first;
 
            if (visited[nextNode] == -1 || visited[nextNode] > cost + nextCost) {
                visited[nextNode] = cost + nextCost;
                pq.push({ cost + nextCost,nextNode });
            }
        }
    }
 
    sort(visited, visited + N);
 
    int cur = 0;
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        if (visited[i] * 2 > X) {
            cout << -1;
            return 0;
        }
        
        cur += visited[i] * 2;
 
        if (cur > X) {
            ans++;
            cur = visited[i] * 2;
        }
    }
 
    cout << ans + 1;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 3067번 - Coins (C++)  (0) 2023.08.18
[ 백준 ] 16965번 - 구간과 쿼리 (C++)  (0) 2023.08.17
[ 백준 ] 2224번 - 명제 증명 (C++)  (0) 2023.08.15
[ 백준 ] 20182번 - 골목 대장 호석 - 효율성 1 (C++)  (0) 2023.08.14
[ 백준 ] 20168번 - 골목 대장 호석 - 기능성 (C++)  (0) 2023.08.13
반응형

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

 

20182번: 골목 대장 호석 - 효율성 1

첫 줄에 교차로 개수 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
70
#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[21][100001];
vector<pair<int,int>> list[100001];
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 <= 20; 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 (shame >= ans) 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
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20007번 - 떡 돌리기 (C++)  (0) 2023.08.16
[ 백준 ] 2224번 - 명제 증명 (C++)  (0) 2023.08.15
[ 백준 ] 20168번 - 골목 대장 호석 - 기능성 (C++)  (0) 2023.08.13
[ 백준 ] 16472번 - 고냥이 (C++)  (0) 2023.08.12
[ 백준 ] 9024번 - 두 수의 합 (C++)  (0) 2023.08.11
반응형

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
반응형

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

 

14497번: 주난의 난(難)

주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited[ 301 ][ 301 ] 배열을 만들어 각 노드의 방문을 기록해 줍니다.

 

2. arr 배열에 교실을 입력받고, bfs를 활용하여 queue에 주난이의 위치를 넣은 다음 1을 만나면 0으로 바꾸어주고, 0을 만나면 queue에 그 좌표를 넣어주고, #을 만나면 점프한 횟수를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int x, y, x2, y2;
int visited[301][301];
char arr[301][301];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
 
int main()
{
    scanf("%d %d", &N, &M);
 
    scanf("%d %d %d %d", &x, &y, &x2, &y2);
 
    for (int i = 0; i < N; i++ ) {
        scanf("%s", arr[i]);
    }
 
    queue<pair<int, int>>q;
 
    int cnt = 0;
 
    while (1) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visited[i][j] = 0;
            }
        }
        cnt++;
        q.push({ x - 1, y - 1 });
        visited[x - 1][y - 1] = 1;
 
        while (!q.empty()) {
            const int x = q.front().first;
            const int y = q.front().second;
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int xx = x + dx[i];
                int yy = y + dy[i];
 
                if (xx >= 0 && xx < N && yy >= 0 && yy < M) {
                    if (visited[xx][yy] != 1) {
                        visited[xx][yy] = 1;
                        if (arr[xx][yy] == '1') {
                            arr[xx][yy] = '0';
                        }
                        else if (arr[xx][yy] == '0') {
                            q.push({ xx,yy });
                        }
                        else {
                            printf("%d", cnt);
                            return 0;
                        }
                    }
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2669번 - 직사각형 네개의 합집합의 면적 구하기 (C++)  (0) 2023.06.18
[ 백준 ] 2164번 - 카드2 (C++)  (0) 2023.06.17
[ 백준 ] 10464번 - XOR (C++)  (0) 2023.06.15
[ 백준 ] 7490번 - 0 만들기 (C++)  (0) 2023.06.14
[ 백준 ] 20437번 - 문자열 게임 2 (C++)  (0) 2023.06.13
반응형

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

 

1800번: 인터넷 설치

첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited[ N ][ K ] 배열을 만들어 인터넷을 K번 공짜로 연결했을 때 해당 노드까지의 연결 값 중 최댓값을 저장합니다.

 

2. dijkstra를 통해 공짜로 연결했을 때와 하지 않았을 때 각각 priority_queue에 넣어줍니다.

 

3. N번 도시에 도착했을 때 dist를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
struct node {
    int cur;
    int cost;
    int cnt;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.cost < right.cost;
    }
};
 
int N, P, K;
vector<pair<int, int>> list[1001];
int visited[1001][1001];
 
int main()
{
    scanf("%d %d %d", &N, &P, &K);
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < N; j++) {
            visited[i][j] = 1111111111;
        }
    }
 
    for (int i = 0; i < P; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
 
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    priority_queue<node, vector<node>, cmp> pq;
    vector<int> temp;
 
    pq.push({ 1,0,0 });
 
    while (!pq.empty()) {
        const int cur = pq.top().cur;
        const int cost = pq.top().cost;
        const int cnt = pq.top().cnt;
        pq.pop();
 
        if (visited[cur][cnt] < cost) continue;
        visited[cur][cnt] = cost;
 
        if (cur == N) {
            printf("%d", cost);
            return 0;
        }
 
        for (auto& next : list[cur]) {
            const int nNode = next.first;
            const int nCost = next.second;
 
            if (cnt < K) {
                if (visited[nNode][cnt + 1] > cost) {
                    pq.push({ nNode,cost,cnt+1 });
                }
            }
 
            if (visited[nNode][cnt] > max(cost, nCost)) {
                pq.push({ nNode,max(cost,nCost),cnt });
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9879번 - Cross Country Skiing (C++)  (0) 2023.05.16
[ 백준 ] 2310번 - 어드벤처 게임 (C++)  (0) 2023.05.15
[ 백준 ] 2820번 - 자동차 공장 (C++)  (0) 2023.05.13
[ 백준 ] 16404번 - 주식회사 승범이네 (C++)  (0) 2023.05.12
[ 백준 ] 14288번 - 회사 문화 4 (C++)  (0) 2023.05.11
반응형

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

 

9370번: 미확인 도착지

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. s, g, h 노드에서 각각의 다익스트라를 구현하여 각각의 노드에서의 최단거리를 저장합니다.

 

2. s -> g -> h -> t 까지의 거리와 s -> t 까지의 거리가 같거나 s -> h -> g -> t 까지의 거리와 s -> t 까지의 거리가 같으면 t를 출력합니다.

 

[ 소스코드 ]

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct node {
    int to;
    int dist;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.dist < right.dist;
    }
};
 
vector<pair<int, int>> list[2001];
 
int n, m, t;
int s, g, h;
int visiteds[2001];
int visitedg[2001];
int visitedh[2001];
int des[100];
int dist;
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int tc = 0; tc < T; tc++) {
 
        priority_queue<node, vector<node>, cmp> pq;
 
        scanf("%d %d %d", &n, &m, &t);
        scanf("%d %d %d", &s, &g, &h);
 
        for (int i = 1; i <= n; i++) {
            visiteds[i] = 987654321;
            visitedg[i] = 987654321;
            visitedh[i] = 987654321;
            list[i].clear();
        }
 
        for (int i = 0; i < m; i++) {
            int a, b, d;
            scanf("%d %d %d", &a, &b, &d);
 
            list[a].push_back({ b,d });
            list[b].push_back({ a,d });
        }
 
        for (int i = 0; i < t; i++) {
            scanf("%d", &des[i]);
        }
 
        sort(des, des + t);
 
        pq.push({ s,0 });
 
        while (!pq.empty()) {
            const int cur = pq.top().to;
            const int dist = pq.top().dist;
            pq.pop();
 
            if (visiteds[cur] < dist) continue;
            visiteds[cur] = dist;
 
            for (auto& next : list[cur]) {
                const int nextNode = next.first;
                const int nextDist = next.second;
 
                if (visiteds[nextNode] > nextDist + dist) {
                    visiteds[nextNode] = nextDist + dist;
                    pq.push({ nextNode,nextDist + dist });
                }
            }
        }
 
        pq.push({ g,0 });
 
        while (!pq.empty()) {
            const int cur = pq.top().to;
            const int dist = pq.top().dist;
            pq.pop();
 
            if (visitedg[cur] < dist) continue;
            visitedg[cur] = dist;
 
            for (auto& next : list[cur]) {
                const int nextNode = next.first;
                const int nextDist = next.second;
 
                if (visitedg[nextNode] > nextDist + dist) {
                    visitedg[nextNode] = nextDist + dist;
                    pq.push({ nextNode,nextDist + dist });
                }
            }
        }
 
        pq.push({ h,0 });
 
        while (!pq.empty()) {
            const int cur = pq.top().to;
            const int dist = pq.top().dist;
            pq.pop();
 
            if (visitedh[cur] < dist) continue;
            visitedh[cur] = dist;
 
            for (auto& next : list[cur]) {
                const int nextNode = next.first;
                const int nextDist = next.second;
 
                if (visitedh[nextNode] > nextDist + dist) {
                    visitedh[nextNode] = nextDist + dist;
                    pq.push({ nextNode,nextDist + dist });
                }
            }
        }
 
        for (int i = 0; i < t; i++) {
            if ((visiteds[g] + visitedg[h] + visitedh[des[i]] == visiteds[des[i]]) || (visiteds[h] + visitedh[g] + visitedg[des[i]] == visiteds[des[i]])) {
                printf("%d ", des[i]);
            }
        }
 
        printf("\n");
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 10836번 - 여왕벌 (C++)  (0) 2023.04.28
[ 백준 ] 2513번 - 통학버스 (C++)  (0) 2023.04.27
[ 백준 ] 2671번 - 잠수함식별 (C++)  (0) 2023.04.25
[ 백준 ] 17218번 - 비밀번호 만들기 (C++)  (0) 2023.04.24
[ 백준 ] 6987번 - 월드컵 (C++)  (0) 2023.04.23

+ Recent posts

티스토리툴바