백준/11657/벨만-포드/타임머신

백준/11657/벨만-포드/타임머신

문제 해석

1번 도시에서 출발하여 각 도시로 가는 최단 거리를 구하는 문제입니다.
이 때, 문제 A에서 B로 가는 거리가 음수일 경우에는 시간을 빼는 문제입니다.

문제 풀이

다익스트라로 풀기에는 가중치에 음수가 들어가므로 벨만-포드를 사용하여 문제를 해결 했습니다.
1. 거리 배열을 초기화하고 출발 도시는 0으로 초기화합니다.
2. 거리 배열에서 아직 초기화 되지 않은 노드를 제외하고 전체 간선을 돌아봅니다.
3. 2번을 노드의 개수 만큼 반복하고 마지막 반복때 dist 배열이 변경 된다면, 해당 그래프는 음수 사이클을 가지고 있다고 판단합니다.

풀이

첫번째 풀이

#include<iostream>
#include<queue>
#include<tuple>
using namespace std;

vector<tuple<int, int, int>>v;

int dist[501];
int INF = 0x3f3f3f3f;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	// N은 도시의 수 ,M은 간선의 수
	int N, M = 0;

	cin >> N >> M;

	for (int i = 1;i <= N;i++)
	{
		dist[i] = INF;
	}

	for (int i = 0;i < M;i++)
	{
		int A, B, C = 0;
		cin >> A >> B >> C;
		v.push_back({ A,B,C });
	}

	dist[1] = 0;

	int flag = true;
	for (int i = 1;i <= N;i++)
	{
		for (int j = 0;j < M;j++)
		{
			int _st, _en, _cost = 0;
			tie(_st, _en, _cost) = v[j];
			if (dist[_st] != INF)
			{
				if (dist[_en] > dist[_st] + _cost)
				{
					dist[_en] = dist[_st] + _cost;
					if (i == N)
						flag = false;
				}
			}
		}
	}

	if (flag)
	{
		for (int i = 2;i <= N;i++)
		{
			if (dist[i] == INF)
			{
				cout << -1 << '\n';
			}
			else
			{
				cout << dist[i] << '\n';
			}
		}
	}
	else
	{
		cout << -1 << '\n';
	}
	


	return 0;
}

두번째 풀이

#include<iostream>
#include<queue>
#include<tuple>
using namespace std;

vector<tuple<int, int, int>>v;

long long dist[501];
int INF = 0x3f3f3f3f;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	// N은 도시의 수 ,M은 간선의 수
	int N, M = 0;

	cin >> N >> M;

	for (int i = 1;i <= N;i++)
	{
		dist[i] = INF;
	}

	for (int i = 0;i < M;i++)
	{
		int A, B, C = 0;
		cin >> A >> B >> C;
		v.push_back({ A,B,C });
	}

	dist[1] = 0;

	int flag = true;
	for (int i = 1;i <= N;i++)
	{
		for (int j = 0;j < M;j++)
		{
			int _st, _en, _cost = 0;
			tie(_st, _en, _cost) = v[j];
			if (dist[_st] != INF)
			{
				if (dist[_en] > dist[_st] + _cost)
				{
					dist[_en] = dist[_st] + _cost;
					if (i == N)
						flag = false;
				}
			}
		}
	}

	if (flag)
	{
		for (int i = 2;i <= N;i++)
		{
			if (dist[i] == INF)
			{
				cout << -1 << '\n';
			}
			else
			{
				cout << dist[i] << '\n';
			}
		}
	}
	else
	{
		cout << -1 << '\n';
	}
	


	return 0;
}