BOJ 1865, 웜홀
ProblemSolving ·이 문제는 벨만포드문제입니다.
풀이
기본 벨만포드 알고리즘을 이용하였습니다. 출발점으로 다시 돌아오는데 시간이 줄어들면 YES 아니면 NO를 출력하는 문제입니다. 이것을 판단하는 것은 음수사이클의 유무로 하였습니다.
특이점으로 dist배열을 갱신하는 조건문에 dist[next]!=1e9 라는 조건이 없습니다. 기존의 벨만포드 알고리즘과 다른 부분이죠. 그 이유는 이 문제는 출발점까지 되돌아와야 합니다. dist[next]!=1e9라는 조건문이 있으면 출발점으로 되돌아오지 못하는 상황에서도 음수사이클이 생겼을 때 YES를 출력하게 되는 오류가 생깁니다.
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
bool cycle;
typedef pair <int, int> P;
int n, m, a, b, c, t, h, dist[505];
vector<vector<P>> adj(505);
int main()
{
scanf("%d", &t);
for (int z = 1; z <= t; z++)
{
scanf("%d %d %d", &n, &m, &h);
adj.clear();
adj.resize(n + 1);
for (int i = 1; i <= m; i++)
{
scanf("%d %d %d", &a, &b, &c);
adj[a].push_back({ b,c });
adj[b].push_back({ a,c });
}
for (int i = 1; i <= h; i++)
{
scanf("%d %d %d", &a, &b, &c);
adj[a].push_back({ b,-c });
}
for (int i = 1; i <= n; i++) dist[i] = 1e9;
dist[1] = 0;
bool cycle = 0;
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 0; j < adj[i].size(); j++)
{
int next = adj[i][j].first;
int nextcost = adj[i][j].second;
if (dist[next] > dist[i] + nextcost)
{
dist[next] = dist[i] + nextcost;
if (k == n) cycle = 1;
}
}
if (cycle == 1) printf("YES\n");
else printf("NO\n");
}
return 0;
}