[최단경로 단계] 백준 11657번 타임머신

문제

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)가 주어진다. 

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

 

 

밸만포드 알고리즘 => 음수 가중치를 처리하기 위함

계속 갱신하면서 음수로 내려가는 것을 처리하기 위해서 정점개수 만큼 횟수를 반복하면서 끝까지 갱신이 되는 지 확인해야 한다.

만약 정점만큼의 iterator에서 끝까지 정점만큼 반복되면 음수.

갱신이 더이상 이뤄지지 않고 끝나면 그대로 출력 가능.

#include <iostream>
#include <vector>
#include<string.h>
#include<queue>
#include <string>
#include<stack>
#include<cmath>
#include <map>
#include<algorithm>
using namespace std;

const int INF = 987654321;
int V, E;
vector<pair<int, int> > vec[501];
vector<long long> bellmanFord(int src)
{
	vector<long long> upper(V + 1, 99999999);
	upper[src] = 0;
	bool updated;

	for (int iter = 1; iter <= V; ++iter)
	{
		updated = false;
		for (int here = 1; here <= V; ++here)
		{
			for (int i = 0; i < (int)vec[here].size(); i++)
			{
				int there = vec[here][i].first;
				int cost = vec[here][i].second;

				if (upper[there] > upper[here] + cost && upper[here] != 99999999 && here != there)
				{
					upper[there] = upper[here] + cost;
					updated = true;
				}
			}
		}
		if (!updated)break;
	}
	if (updated)upper.clear();
	return upper;
}



int main() {

	
	cin >> V >> E;
	for (int i = 0; i < E; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		vec[a].push_back({ b,c });
	}
		
	vector<long long> res = bellmanFord(1);
	if (res.size() == 0) {
		cout << -1;
	}
	else {

		for (int i = 2; i < (int)res.size(); ++i) {
			if (res[i] == 99999999) {
				cout << -1;
			}
			else cout << res[i];

			if (i != res.size() - 1) cout << endl;
		}


	}
	
}