알고리즘 문제풀이/백준
[백준 11657] 타임 머신
홍시홍
2020. 1. 14. 00:29
https://www.acmicpc.net/problem/11657
11657번: 타임머신
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
www.acmicpc.net
요구사항
음의 경로가 있는지 확인(벨만 포드)
풀이
모든 노드에 대해서 간선만큼 반복하여 최저 경로를 갱신한다
모든 노드에 대해서 탐색하고 한번 더 탐색하였을 때, 감소되는 경로가 있으면 음의 경로가 존재하는 것이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct go {
int x;
int y;
};
int n, m;
int dist[501];
vector<go> v[501];
const int INF = 0x7fffffff;
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
v[x].push_back({ y,z });
}
for (int i = 1; i <= n; i++) {
dist[i] = INF;
}
dist[1] = 0;
int flag = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (auto p : v[j]) {
int next = p.x;
int D = p.y;
// cout << next << " " << D << endl;
if (dist[j] != INF && dist[next] > dist[j] + D)
{
dist[next] = dist[j] + D;
if (i == n) flag = 1;
}
}
}
}
if (flag == 1)
cout << "-1" << endl;
else {
for (int i = 2; i <= n; i++) {
printf("%d\n", dist[i] != INF ? dist[i] : -1);
}
}
}