https://www.acmicpc.net/problem/1865
#include<iostream>
#include<vector>
#define INF 10000000
using namespace std;
int N;
int M;
int dist[501];
vector<pair<int, int>> a[501];
bool Bellman_Ford(){
for(int i = 0; i <= N; i++){
dist[i] = INF;
}
dist[1] = 0;
bool table = false;
for(int i = 0; i <= N-1; i++){ // N번을 반복할 것
for(int j = 1; j<=N; j++){ //N개의 노드를 확인
for(int k = 0; k < a[j].size(); k++){ // 선택된 j의 간선
int next = a[j][k].first;
int weight = a[j][k].second;
if(dist[next] > dist[j] + weight){//최소비용 갱신
dist[next] = dist[j] + weight;
if(i == N-1){
table = true; /*N-1번째 반복일때도 최소비용이 갱신된다면
음의 사이클을 가짐*/
}
}
}
}
}
return table;
}
int main(){
int Testcase;
int W;
int S;
int E;
int T;
cin>>Testcase;
for(int i = 0; i < Testcase; i++){
cin>>N>>M>>W;
for(int j = 0; j < M; j++){
cin>>S>>E>>T;
a[S].push_back({E, T});
a[E].push_back({S, T});
}
for(int k = 0; k < W; k++){
cin>>S>>E>>T;
a[S].push_back({E, -T});
}
if(Bellman_Ford()){
cout<<"YES"<<'\n';
}else{
cout<<"NO"<<'\n';
}
for(int i = 0; i <= N; i++){
a[i].clear();
}
}
return 0;
}
음의 가중치가 존재하기 때문에 다익스트라 알고리즘으로는 이 문제를 해결할 수 없었습니다.
이 문제를 풀기 위해서는 벨만포드 알고리즘이 사용됩니다.
음의 사이클이 존재한다는 것은 출발점으로 돌아왔을 때 시간이 되돌아갈 수 있다는 뜻 입니다.
'BOJ 백준 > Class 4' 카테고리의 다른 글
백준 17070번, 파이프 옮기기 1(C, C++) (0) | 2022.01.24 |
---|---|
백준 12865번, 평범한 배낭 (0) | 2022.01.24 |
백준 1238번, 파티(C, C++) (0) | 2022.01.21 |
백준 1932번, 정수 삼각형(C, C++) (0) | 2022.01.21 |
백준 1629, 곱셉(C, C++) (0) | 2022.01.21 |