반응형

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

+ Recent posts

티스토리툴바