https://www.acmicpc.net/problem/1865
목적
음의 가중치가 존재하는 방향 그래프에서 음의 사이클이 존재하는지 알아내자.
접근법
1. 최단 거리를 구하기 위해 흔히 알려진 3가지 알고리즘 중에 음의 가중치가 존재할 때 최단 거리를 O(VE)의 시간복잡도로 구할 수 있는 '벨만 포드'로 접근하자.
2. 출발지로부터 모든 정점으로의 최단거리를 갱신하면서, 출발지인 정점 1의 최단 거리가 음수가 되는 순간, 음의 사이클이 존재한다는 결론으로 귀결난다.
3. V번째 loop를 돌고 값의 갱신 여부를 확인한다.
#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
int n,m,w,size,edge[5201][3],d[501];
bool sol(){
f(i,1,n)d[i]=5e6;
d[1]=0;
int cnt=size;
bool updated;
while(cnt--){
updated=false;
f(j,1,size){
int tmp=d[edge[j][0]]+edge[j][2];
if(d[edge[j][1]]>tmp){
if(edge[j][1]==1)return true;
d[edge[j][1]]=tmp,updated=true;
}
}
if(!updated)return false;
}
return updated;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc;cin>>tc;
while(tc--){
cin>>n>>m>>w;
size=0;
while(m--){
int s,e,t;cin>>s>>e>>t;
size+=2;
edge[size-1][0]=edge[size][1]=s;
edge[size-1][1]=edge[size][0]=e;
edge[size-1][2]=edge[size][2]=t;
}
while(w--){
int s,e,t;cin>>s>>e>>t;
++size;
edge[size][0]=s;
edge[size][1]=e;
edge[size][2]=-t;
}
cout<<(sol()?"YES":"NO")<<'\n';
}
return 0;
}
문제 설명과 코드에 대한 피드백은 언제나 환영합니다.
다양한 의견 댓글로 남겨주세요.
'Problem Solving > BOJ 백준' 카테고리의 다른 글
[ BOJ 백준 4803번 - 트리 ] 해설 및 코드 (0) | 2019.12.30 |
---|---|
[ BOJ 백준 11725번 - 트리의 부모 찾기 ] 해설 및 코드 (0) | 2019.12.30 |
[ BOJ 백준 1238번 - 파티 ] 해설 및 코드 (0) | 2019.12.29 |
[ BOJ 백준 11657번 - 타임머신 ] 해설 및 코드 (0) | 2019.12.29 |
[ BOJ 백준 10159번 - 저울 ] 해설 및 코드 (0) | 2019.12.29 |