반응형

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

 

13424번: 비밀 모임

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

 

1. arr[ N ][ N ] 배열을 만들어 각 노드까지의 거리를 저장해 줍니다.

 

2. 플로이드 와샬 알고리즘을 이용하여 각 노드 간의 최단거리를 저장해 줍니다.

 

3. 1부터 N까지 K개의 방에서부터 i까지의 거리를 모두 더해주고, 그 값들 중 가장 작은 값을 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
#include<iostream>
 
using namespace std;
 
int arr[101][101];
int room[101];
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int N, M, K;
        scanf("%d %d", &N, &M);
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    arr[i][j] = 0;
                }
                else {
                    arr[i][j] = 987654321;
                }
            }
        }
 
        for (int i = 0; i < M; i++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            arr[a][b] = c;
            arr[b][a] = c;
        }
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k <= N; k++) {
                    arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
                }
            }
        }
 
        scanf("%d", &K);
        int dist = 987654321;
        int ans = 0;
 
        for (int i = 0; i < K; i++) {
            scanf("%d", &room[i]);
        }
 
        for (int i = 1; i <= N; i++) {
            int temp = 0;
            for (int j = 0; j < K; j++) {
                temp += arr[i][room[j]];
            }
            if (dist > temp) {
                dist = temp;
                ans = i;
            }
        }
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1321번 - 군인 (C++)  (0) 2023.04.04
[ 백준 ] 14728번 - 벼락치기 (C++)  (0) 2023.04.03
[ 백준 ] 1719번 - 택배 (C++)  (0) 2023.04.01
[ 백준 ] 13023번 - ABCDE (C++)  (0) 2023.03.31
[ 백준 ] 17490번 - 일감호에 다리 놓기 (C++)  (0) 2023.03.30
반응형

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

 

1719번: 택배

첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

 

1. arr[ n ][ n ] 배열을 만들어 각 노드까지의 거리를 저장해 줍니다.

 

2. ans[ n ][ n ] 배열을 만들어 각 노드까지 갈 때 가장 처음으로 거치는 노드를 저장해 줍니다.

 

3. 플로이드 와샬 알고리즘을 이용하여 각 노드 간의 최단거리를 저장해 주고, 최단거리를 갱신할 때 ans[ j ][ k ] = ans[ j ][ i ]를 같이 처리해 줍니다.

 

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
#include<iostream>
 
using namespace std;
 
int n, m;
int arr[201][201];
int ans[201][201];
 
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j) {
                arr[i][j] = 987654321;
            }
        }
    }
 
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
 
        ans[a][b] = b;
        ans[b][a] = a;
        arr[a][b] = c;
        arr[b][a] = c;
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (arr[j][i] != 0 && arr[i][k] != 0) {
                    if (arr[j][k] > arr[j][i] + arr[i][k]) {
                        arr[j][k] = arr[j][i] + arr[i][k];
                        ans[j][k] = ans[j][i];
                    }
                }
            }
        }
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                printf("- ");
            }
            else {
                printf("%d ", ans[i][j]);
            }
        }
        printf("\n");
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14728번 - 벼락치기 (C++)  (0) 2023.04.03
[ 백준 ] 13424번 - 비밀 모임 (C++)  (0) 2023.04.02
[ 백준 ] 13023번 - ABCDE (C++)  (0) 2023.03.31
[ 백준 ] 17490번 - 일감호에 다리 놓기 (C++)  (0) 2023.03.30
[ 백준 ] 14921번 - 용액 합성하기 (C++)  (0) 2023.03.29
반응형

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

 

23286번: 허들 넘기

첫째 줄에 세 정수 N, M, T가 주어진다. 다음 M개의 줄에 그래프 간선의 정보 u, v, h가 주어지고, u에서 v로 가는 간선이 있고, 높이가 h인 허들이 간선 중간에 놓여 있다는 의미이다. 마지막 T개의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

1. arr[ N ][ N ] 배열을 만들어서 값을 987654321로 초기화해 줍니다.

 

2. 플로이드 와샬 알고리즘을 이용하여 이동 구간 중 가장 높은 허들의 높이가 가장 낮은 값으로 arr 배열을 갱신합니다.

 

3. arr[ u ][ v ]의 값이 987654321이라면 -1을 아니라면 arr[ u ][ v ]를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M, T;
int arr[301][301];
 
int main()
{
    scanf("%d %d %d", &N, &M, &T);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            arr[i][j] = 987654321;
        }
    }
 
    for (int i = 0; i < M; i++) {
        int u, v, h;
        scanf("%d %d %d", &u, &v, &h);
 
        arr[u][v] = h;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                arr[j][k] = min(arr[j][k], max(arr[j][i], arr[i][k]));
            }
        }
    }
 
    for (int i = 0; i < T; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
 
        if (arr[u][v] == 987654321) {
            printf("-1\n");
        }
        else {
            printf("%d\n", arr[u][v]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1781번 - 컵라면 (C++)  (0) 2023.03.27
[ 백준 ] 15989번 - 1, 2, 3 더하기 4 (C++)  (0) 2023.03.26
[ 백준 ] 15422번 - Bumped! (C++)  (0) 2023.03.24
[ 백준 ] 21940번 - 가운데에서 만나기 (C++)  (0) 2023.03.23
[ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++)  (0) 2023.03.22
반응형

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

 

15422번: Bumped!

The input consists of a single test case. The first line lists five space-separated integers n, m, f, s, and t, denoting the number of cities n (0 < n ≤ 50 000), the number of roads m (0 ≤ m ≤ 150 000), the number of flights f (0 ≤ f ≤ 1 000), th

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited[ n ][ used ] 배열을 만들어 비행기 표를 썼을 때와 쓰지 않았을 때 이동 거리를 visited 배열에 저장합니다.

 

2. dijkstra를 활용하여 s부터 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
#include<iostream>
#include<vector>
#include<queue>
#define ll long long
 
using namespace std;
 
struct node {
    int cur;
    ll cost;
    int used;
};
 
struct cmp {
    bool operator()(node right, node left)
    {
        return left.cost < right.cost;
    }
};
 
int n, m, f, s, t;
vector<pair<int, int>> list[50000];
ll visited[50000][2];
 
int main()
{
    scanf("%d %d %d %d %d", &n, &m, &f, &s, &t);
    for (int i = 0; i < n; i++) {
        visited[i][0] = visited[i][1] = 3333333333;
    }
 
    for (int i = 0; i < m; i++) {
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);
 
        list[u].push_back({ v,c });
        list[v].push_back({ u,c });
    }
 
    for (int i = 0; i < f; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
 
        list[u].push_back({ v,0 });
    }
 
    priority_queue<node, vector<node>, cmp> pq;
 
    pq.push({ s,0,0 });
 
    while (!pq.empty()) {
        const int cur = pq.top().cur;
        const ll cost = pq.top().cost;
        const int used = pq.top().used;
        pq.pop();
 
        if (visited[cur][used] < cost) continue;
        visited[cur][used] = cost;
 
        if (cur == t) {
            printf("%lld", cost);
            return 0;
        }
 
        for (auto& next : list[cur]) {
            if (used == 0 && next.second == 0) {
                if (visited[next.first][1] > cost) {
                    visited[next.first][1] = cost;
                    pq.push({ next.first, cost, 1 });
                }
            }
            else if (next.second != 0) {
                if (visited[next.first][used] > cost + next.second) {
                    visited[next.first][used] = cost + next.second;
                    pq.push({ next.first, visited[next.first][used], used});
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15989번 - 1, 2, 3 더하기 4 (C++)  (0) 2023.03.26
[ 백준 ] 23286번 - 허들 넘기 (C++)  (0) 2023.03.25
[ 백준 ] 21940번 - 가운데에서 만나기 (C++)  (0) 2023.03.23
[ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++)  (0) 2023.03.22
[ 백준 ] 4963번 - 섬의 개 (C++)  (0) 2023.03.21
반응형

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

 

5972번: 택배 배송

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dijkstra를 활용하여 1부터 N까지 이동합니다.

 

2. 이동거리를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int N, M;
vector<pair<int, int>> list[50001];
int visited[50001];
 
int main()
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    scanf("%d %d", &N, &M);
 
    fill(visited, visited + N + 1, 987654321);
 
    for (int i = 0; i < M; i++) {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);
 
        list[A].push_back({ B,C });
        list[B].push_back({ A,C });
    }
 
    pq.push({ 0,1 });
 
    while (!pq.empty()) {
        const int cur = pq.top().second;
        const int dist = pq.top().first;
        pq.pop();
 
        if (cur == N) {
            printf("%d", dist);
            return 0;
        }
 
        if (visited[cur] < dist) continue;
        visited[cur] = dist;
 
        for (auto& next : list[cur]) {
            const int nNode = next.first;
            const int nDist = next.second;
 
            if (visited[nNode] > dist + nDist) {
                visited[nNode] = dist + nDist;
                pq.push({ visited[nNode], nNode });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 21924번 - 도시 건설 (C++)  (0) 2023.03.06
[ 백준 ] 13905번 - 세부 (C++)  (0) 2023.03.05
[ 백준 ] 14284번 - 간선 이어가기 2 (C++)  (0) 2023.03.03
[ 백준 ] 17396번 - 백도어 (C++)  (0) 2023.03.02
[ 백준 ] 3066번 - 브리징 시그널 (C++)  (0) 2023.03.01
반응형

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

 

14284번: 간선 이어가기 2

정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dijkstra를 활용하여 s부터 t까지 이동합니다.

 

2. 이동거리를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int n, m, s, t;
vector<pair<int, int>> list[5001];
int visited[5001];
 
int main()
{
    scanf("%d %d", &n, &m);
 
    fill(visited, visited + n + 1, 987654321);
 
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    scanf("%d %d", &s, &t);
 
    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 == t) {
            printf("%d", dist);
            return 0;
        }
 
        if (visited[cur] < dist) continue;
        visited[cur] = dist;
 
        for (auto& next : list[cur]) {
            const int nextNode = next.first;
            const int nextDist = next.second;
 
            if (visited[nextNode] > dist + nextDist) {
                visited[nextNode] = dist + nextDist;
                pq.push({ visited[nextNode], nextNode });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13905번 - 세부 (C++)  (0) 2023.03.05
[ 백준 ] 5972번 - 택배 배송 (C++)  (0) 2023.03.04
[ 백준 ] 17396번 - 백도어 (C++)  (0) 2023.03.02
[ 백준 ] 3066번 - 브리징 시그널 (C++)  (0) 2023.03.01
[ 백준 ] 2660번 - 회장뽑기 (C++)  (0) 2023.02.28
반응형

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

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

 

1162번: 도로포장

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하

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
#include<iostream>
#include<queue>
#include<vector>
#define ll long long
 
using namespace std;
 
struct node {
    int cur;
    ll dist;
    int K;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.dist < right.dist;
    }
};
 
int N, M, K;
ll visited[10001][21];
vector<pair<int, ll>> list[10001];
 
int main()
{
    priority_queue<node, vector<node>, cmp>pq;
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 2; i <= N; i++) {
        for (int j = 0; j <= K; j++) {
            visited[i][j] = 9222222222222222222;
        }
    }
 
    for (int i = 0; i < M; i++) {
        int u, v;
        ll c;
        scanf("%d %d %lld", &u, &v, &c);
        list[u].push_back({ v,c });
        list[v].push_back({ u,c });
    }
 
    pq.push({ 1,0,0 });
 
    while (!pq.empty()) {
        const int cur = pq.top().cur;
        const ll dist = pq.top().dist;
        const int cnt = pq.top().K;
        pq.pop();
 
        if (visited[cur][cnt] < dist) continue;
 
        if (cur == N) {
            printf("%lld", dist);
            return 0;
        }
 
        for (auto& next : list[cur]) {
            const int nextNode = next.first;
            const ll nextDist = next.second;
            if (cnt < K) {
                if (visited[nextNode][cnt + 1] > dist) {
                    visited[nextNode][cnt + 1] = dist;
                    pq.push({ nextNode,dist,cnt + 1 });
                }
            }
            
            if (visited[nextNode][cnt] > dist + nextDist) {
                visited[nextNode][cnt] = dist + nextDist;
                pq.push({ nextNode,dist + nextDist,cnt });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 18405번 - 경쟁적 전염 (C++)  (0) 2023.02.25
[ 백준 ] 1613번 - 역사 (C++)  (0) 2023.02.24
[ 백준 ] 6497번 - 전력난 (C++)  (0) 2023.02.22
[ 백준 ] 18223번 - 민준이와 마산 그리고 건우 (C++)  (0) 2023.02.21
[ 백준 ] 2056번 - 작업 (C++)  (0) 2023.02.20
반응형

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

 

18223번: 민준이와 마산 그리고 건우

입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V  ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P  ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dijkstra 함수를 만들어서 a번 정점에서 b번 정점까지 가는 거리를 return 합니다.

 

2. 만약 1번 정점에서 P번 정점까지의 거리와 P번 정점에서 V번 정점까지의 거리의 합이 1번 정점에서 V번 정점까지의 거리와 같다면 SAVE HIM을 출력하고, 그렇지 않다면 GOOD BYE를 출력합니다.

 

[ 소스코드 ]

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>
 
using namespace std;
 
int V, E, P;
int visited[5001];
vector<pair<int, int>> list[5001];
 
int dijkstra(int a, int b)
{
    fill(visited, visited + V + 1, 987654321);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
 
    pq.push({ 0,a });
    visited[a] = 0;
 
    while (!pq.empty()) {
        const int cur = pq.top().second;
        const int dist = pq.top().first;
        pq.pop();
 
        if (cur == b) {
            return dist;
        }
 
        for (auto& next : list[cur]) {
            const int nextNode = next.first;
            const int nextDist = next.second;
            if (visited[nextNode] > dist + nextDist) {
                visited[nextNode] = dist + nextDist;
                pq.push({ visited[nextNode], nextNode });
            }
        }
    }
}
 
int main()
{
    scanf("%d %d %d", &V, &E, &P);
 
    for (int i = 0; i < E; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    if (dijkstra(1, P) + dijkstra(P, V) == dijkstra(1, V)) {
        printf("SAVE HIM");
    }
    else {
        printf("GOOD BYE");
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1162번 - 도로포장 (C++)  (0) 2023.02.23
[ 백준 ] 6497번 - 전력난 (C++)  (0) 2023.02.22
[ 백준 ] 2056번 - 작업 (C++)  (0) 2023.02.20
[ 백준 ] 2406번 - 안정적인 네트워크 (C++)  (0) 2023.02.19
[ 백준 ] 20010번 - 악덕 영주 혜유 (C++)  (0) 2023.02.18
반응형

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

 

2211번: 네트워크 복구

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다

www.acmicpc.net

 

 

[ 문제풀이 ]

1. visited 배열을 만들고 visited [ i ] = 987654321로 초기화해 줍니다.

 

2. node struct를 만들어서 연결된 각각의 컴퓨 번호와 비용을 저장합니다.

 

3. dijkstra를 이용하여 네트워크를 복구하고, 네트워크가 연결될 때마다 ans에 각각의 컴퓨터 번호를 push 해줍니다.

 

4. 연결된 네트워크의 개수를 출력하고, 각각의 번호를 출력합니다.

 

[ 소스코드 ]

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>
#include<vector>
 
using namespace std;
 
int N, M;
vector<pair<int, int>> list[1001];
int visited[1001];
vector<pair<int,int>> ans;
 
struct node {
    int before;
    int cur;
    int cost;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.cost < right.cost;
    }
};
 
int main()
{
    priority_queue<node, vector<node>, cmp> pq;
    scanf("%d %d", &N, &M);
 
    fill(visited, visited + N + 1, 987654321);
    visited[1] = 0;
 
    for (int i = 0; i < M; i++) {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);
        list[A].push_back({ B,C });
        list[B].push_back({ A,C });
    }
 
    pq.push({ 0,1,0 });
 
    while (!pq.empty()) {
        const int before = pq.top().before;
        const int cur = pq.top().cur;
        const int cost = pq.top().cost;
        pq.pop();
 
        if (visited[cur] < cost) continue;
 
        ans.push_back({ before,cur });
 
        for (auto& next : list[cur]) {
            if (visited[next.first] > cost + next.second) {
                visited[next.first] = cost + next.second;
                pq.push({ cur, next.first, cost + next.second });
            }
        }
    }
 
    printf("%d\n", ans.size() - 1);
 
    for (int i = 1; i < ans.size(); i++) {
        printf("%d %d\n", ans[i].first, ans[i].second);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11658번 - 구간 합 구하기 3 (C++)  (0) 2023.02.08
[ 백준 ] 2458번 - 키 순서 (C++)  (0) 2023.02.07
[ 백준 ] 17835번 - 면접보는 승범이네 (C++)  (0) 2023.02.05
[ 백준 ] 1368번 - 물대기 (C++)  (0) 2023.02.04
[ 백준 ] 1261번 - 알고스팟 (C++)  (0) 2023.02.03

+ Recent posts

티스토리툴바