벨만-포드 알고리즘에 대해서 외워서 풀어서 된통 당했다. 이 문제도 코드 한 줄 때문에 계속해서 틀려버렸다. 벨만-포드 알고리즘을 간선 리스트를 활용해서 풀었는데, 코드가 간결하고 좋아서 남겨두고자 하는 목적도 있다. 음의 사이클 판별하는 데 모범적인 코드이다.
벨만-포드 알고리즘은 특정 정점으로부터 다른 모든 정점으로의 최단 거리를 구할 수 있다. 이 문제는 잘 읽어보면 출발점이 특정되어 있지 않다. 문제를 풀기 위해서 각 정점을 출발점으로 하여, 하나씩 사이클의 유무를 확인해보면 된다. 그런데 n <= 500
이므로 절대 올바른 풀이가 아님을 짐작할 수 있다.
그럼 대체 어떻게?
이 문제는 최단 거리 따위는 관심없고, 음의 사이클의 존재 유무만 파악하면 된다. 풀이한 코드는 임의로 1번 정점을 출발점으로 잡았다.
일반적인 벨만-포드 알고리즘처럼 모든 거리를 INF
로 초기화하고 dist[s] != INF
라는 조건을 넣어버리면, 1번 정점에 연결된 간선이 전혀 없을 경우에 다른 정점들은 relax되지 않는다. 다른 정점들의 거리값은 모두 INF
로 유지되고, 음의 사이클이 존재하더라도 위 조건 때문에 알 수 없게 된다.
if (dist[s] != INF && dist[e] > dist[s] + t) X
if (dist[e] > dist[s] + t) o
아래 링크에 더 자세히 설명되어 있다.
#include <iostream>
#include <vector>
using namespace std;
#define INF 5000000
int tc, n, m, w;
bool ncycle;
int dist[501];
class Edge {
public:
int s, e, t;
Edge(int a, int b, int c) {
this->s = a;
this->e = b;
this->t = c;
}
};
vector<Edge> Ed;
bool bellmanFord()
{
dist[1] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < Ed.size(); ++j) {
int s = Ed[j].s;
int e = Ed[j].e;
int t = Ed[j].t;
if (dist[e] > dist[s] + t) { <-----------------------
dist[e] = dist[s] + t;
if (i == n) return true;
}
}
}
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> tc;
for (int k = 1; k <= tc; ++k) {
Ed.clear();
for (int i = 1; i <= n; ++i) dist[i] = INF;
cin >> n >> m >> w;
for (int i = 1; i <= m; ++i) {
int a, b, c; cin >> a >> b >> c;
Ed.push_back(Edge(a, b, c));
Ed.push_back(Edge(b, a, c));
}
for (int i = 1; i <= w; ++i) {
int a, b, c; cin >> a >> b >> c;
Ed.push_back(Edge(a, b, -c));
}
ncycle = bellmanFord();
if (ncycle) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}