N개의 정점이 있고 M개의 방향성이 없는 간선과 W개의 방향성이 있는 그래프가 주어진다.
이때 W는 음수의 가중치를 가지고 있다.
어느 시작점이든 출발을 했을 때보다 시간이 더 적은 경우가 있으면 "YES" 없으면 "NO"를 출력하는 문제이다.
첫 번째 줄에는 테스트케이스의 수 T가 주어진다.
두 번째 줄부터 T개의 테스트케이스가 차례로 주어진다. 각 테스트 케이스의 첫 번째 줄에는 정점의 수 N(1 <= N <= 500), 방향성이 없는 간선의 수 M, 방향성이 있는 간선 W가 주어진다.
그 다음 줄에는 M개의 줄 만큼 방향성이 없는 간선이 차례대로 주어지고 그 다음에는 W개의 줄 만큼 방향성이 있는 간선이 주어진다.
예제 입력
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
예제 출력
NO
YES
어디서 힌트를 얻을 수 있을까?
우선 정점, 간선, 가중치, 그리고 음수라는 키워드를 통해 이 문제는 벨만 포드 알고리즘을 활용하여 문제를 풀 수 있다는 것을 알 수 있었다.
출발점에서 출발 했을 때보다 시간이 되돌아 가는 경우는 즉, 0으로 세팅된 시작점의 거리 dist[S] 더 작은 음수가 나와야 한다는 것이다.
이 말은 다시 말해 계속해서 최단 경로가 갱신될 수 있다는 말이고 음수 싸이클이 존재하냐 안하냐를 판단하는 문제이다.
하지만 출발점이 명확하게 주어지지 않았기 때문에 방문하지 않은 노드를 체크하여 해당 노드만을 검사하는 방식으로 해야 최소한의 시간만 사용하여 문제를 해결할 수 있다.
#include <iostream>
#include <cstring>
#include <vector>
#include <utility>
typedef std::pair<int, int> P;
int INF = 987654321;
long long dist[501];
int bellFord(std::vector<P >* adj, int N, int S)
{
dist[S] = 0;
bool minCircle = false;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (auto& it : adj[j])
{
int there = it.first;
int nCost = it.second;
if (dist[j] != INF && dist[there] > dist[j] + nCost)
{
dist[there] = dist[j] + nCost;
if (i == N - 1)
minCircle = true;
}
}
}
}
return minCircle;
}
void solve(void)
{
int N, M, W;
std::cin >> N >> M >> W;
std::vector<P > adj[N];
for (int i = 0; i < M; i++)
{
int X, Y, C;
std::cin >> X >> Y >> C;
adj[X - 1].push_back(P(Y - 1, C));
adj[Y - 1].push_back(P(X - 1, C));
}
for (int i = 0; i < W; i++)
{
int X, Y, C;
std::cin >> X >> Y >> C;
adj[X - 1].push_back(P(Y - 1, -C));
}
bool flag = false;
for (int i = 0; i < N; i++)
{
if (dist[i] == INF)
{
if (bellFord(adj, N, i))
{
flag = true;
break;
}
}
}
if (flag)
std::cout << "YES" << "\n";
else
std::cout << "NO" << "\n";
}
int main(void)
{
int T;
std::cin >> T;
for (int i = 0; i < T; i++)
{
for (int i = 0; i < 201; i++)
dist[i] = INF;
solve();
}
return 0;
}
https://www.acmicpc.net/problem/1865
1865번: 웜홀
첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500),
www.acmicpc.net
벨만 포드 알고리즘(Bellman-Ford Algorithm)
벨만 포드 알고리즘이란? 벨만 포드 알고리즘(Bellman-Ford Algorithm)은 다익스트라 알고리즘과 마찬가지로 시작점을 정해주면 시작점 기준으로 다른 모든 정점으로의 최단 거리를 구해주는 알고리
deulee.tistory.com
백준 1918 - 후위 표기식(C++) (0) | 2023.05.24 |
---|---|
백준 1916 - 최소비용 구하기(C++) (0) | 2023.05.23 |
백준 12930 - 두 가중치(C++) (0) | 2023.05.23 |
백준 1753 - 최단경로(C++) (0) | 2023.05.22 |
백준 1629 - 곱셈(C++) (0) | 2023.05.22 |