11657>타임머신

https://www.acmicpc.net/problem/11657

밸만 포드 알고리즘

https://ko.wikipedia.org/wiki/%EB%B2%A8%EB%A8%BC-%ED%8F%AC%EB%93%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다. 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

code>>

#include<iostream>

#include<vector>

#include<tuple>

int main()

{

std::vector<std::tuple<int, int, int>> nodes;

int dis[501];

std::ios::ios_base::sync_with_stdio(false);

int N = 3, M = 4, a,b,c;

std::fill(dis, dis + 501, 987654321);

std::cin >> N >> M;

for (int i = 0; i < M; i++)

{

std::cin >> a >> b >> c;

nodes.emplace_back(std::make_tuple(a, b, c));

}

dis[1] = 0;

bool isCycles = false;

for (size_t i = 0; i < N; i++)

{

for (size_t ii = 0; ii < M; ii++)

{

auto p = nodes[ii];

if (dis[std::get<0>(p)] != 987654321 && dis[std::get<1>(p)] > dis[std::get<0>(p)] + std::get<2>(p))

dis[std::get<1>(p)] = dis[std::get<0>(p)] + std::get<2>(p);

}

}

for (size_t i = 0; i < M; i++)

{

auto p = nodes[i];

if (dis[std::get<0>(p)] != 987654321 && dis[std::get<1>(p)] > dis[std::get<0>(p)] + std::get<2>(p))

{

isCycles = true;

break;

}

}

if(isCycles)

printf("-1\n");

else

{

for (int i = 2; i <= N; i++)

printf("%d\n", dis[i] == 987654321 ? -1 : dis[i]);

}

return 0;

}