반응형

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

 

1865번: 웜홀

첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500),

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/22

 

벨만 포드 알고리즘(Bellman-Ford Algorithm)

오늘 설명할 알고리즘은 벨만 포드 알고리즘(Bellman-Ford Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 벨만 포드 알고리즘이 dijkstra보다 시

rudalsd.tistory.com

 

이번 문제에서는 일반적인 최단거리를 구하는 문제들과는 다르게 단순히 음의 cycle이 있는지 없는지만 체크해주면 되는 문제입니다.

 

따라서 일반적인 벨만 포드 알고리즘과 달리 각 노드까지의 거리를 어떤 수로도 초기화시켜주어도 되고, 갱신이 된 적이 없는 노드들도 모두 돌아가면서 거리가 갱신되는지 체크해주면 됩니다.

 

마지막에 거리가 갱신이 된다면 음의 사이클이 존재한다는 뜻이므로 YES를 출력해주면 됩니다.

 

[ 소스 코드 ]

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<vector>
#include<cstring>
 
using namespace std;
 
int N, M, W;
 
struct Node {
    int to;
    int dist;
};
 
int dist[501];
 
int main()
{
    int T;
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        cin >> N >> M >> W;
        vector<Node> list[501];
 
        memset(dist, -1, sizeof(dist));
 
        for (int i = 0; i < M; i++) {
            int S, E, T;
            scanf("%d %d %d", &S, &E, &T);
            list[S].push_back({ E,T });
            list[E].push_back({ S,T });
        }
 
        for (int i = 0; i < W; i++) {
            int S, E, T;
            scanf("%d %d %d", &S, &E, &T);
            list[S].push_back({ E,-T });
        }
 
        int flag = 0;
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                for (int k = 0; k < list[j].size(); k++) {
                    int next = list[j][k].to;
                    int nextDist = list[j][k].dist;
                    if (dist[next] > nextDist + dist[j]) {    //N번째에도 거리가 줄어들었다면 음의 cycle이 있다는 뜻이므로
                        dist[next] = nextDist + dist[j];
                        if (i == N) {
                            flag = 1;
                        }
                    }
                }
            }
        }
 
        if (flag == 1) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13460번 - 구슬 탈출 2 (C++)  (0) 2022.06.12
[ 백준 ] 11404번 - 플로이드 (C++)  (0) 2022.06.11
[ 백준 ] 1238번 - 파티 (C++)  (0) 2022.06.09
[ 백준 ] 12865번 - 평범한 배낭 (C++)  (0) 2022.06.08
[ 백준 ] 9663번 - N-Queen (C++)  (0) 2022.06.07

+ Recent posts

티스토리툴바