백준 11657번 _ 타임머신

2020-05-03 · 배운 것 · 4분 읽기

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

11657번: 타임머신

풀이방법

벨만 포드 알고리즘 사용.
음수 사이클 판별은 n번째에와 n-1번을 비교해서 다르면 음수사이클이 있다고 판단.

주의사항

1. 같은 경로로 여러가지 값이 들어올수 있으므로 최솟값만 저장하게 코드를 작성할것.
2. 거리값이 최대 6000*10000 으로 6억까지 들어올수 있으므로 int로 쓰면 오버플로우 될수있음. long long 추천.

전체코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <map>

#define INF 987654321

using namespace std;
map<pair<int, int>, int> tempEdge;
vector<vector<pair<int, long long>>> edge;
long long city[501];
int N, M;

void cityInit()
{
	for (int i = 1; i <= N; i++)
	{
		city[i] = INF;
	}
	city[1] = 0;
}

void makeEdge()
{
	//간선 가중치의 최솟값을 받기 위해서
	//make edge;
	int s, e, dis;
	for (int i = 0; i < M; i++)
	{
		cin >> s >> e >> dis;
		if (tempEdge.count({ s,e }) == 0)
			tempEdge[{s, e}] = dis;
		else
			tempEdge[{s, e}] = min(tempEdge[{s, e}], dis);
	}

	edge.resize(N + 1);
	for (auto& ele : tempEdge)
	{
		s = ele.first.first;
		e = ele.first.second;
		dis = ele.second;

		edge[s].push_back({ e, dis });
	}
}

void checkEdge()
{
	for (int here = 1; here <= N; here++)
	{
		if (city[here] == INF)
			continue;

		for (auto& ele : edge[here])
		{
			int there = ele.first;
			long long dis = ele.second + city[here];

			if (city[there] > dis)
				city[there] = dis;
		}
	}
}

void bellmanFord()
{
	for (int cnt = 1; cnt <= N-1; cnt++)
	{
		checkEdge();
	}
}

bool isMinusCycle()
{
	vector<long long> tempAns;
	tempAns.resize(1);

	for (int i = 1; i <= N; i++)
	{
		tempAns.push_back(city[i]);
	}

	//음수 순환인지 확인
	checkEdge();

	for (int i = 1; i <= N; i++)
	{
		if (tempAns[i] != city[i])
			return true;
	}

	return false;
}

int main()
{
	cin >> N >> M;
	cityInit();
	makeEdge();
	bellmanFord();
	
	if (isMinusCycle())
		cout << -1 << endl;
	else
	{
		for (int i = 2; i <= N; i++)
		{
			if (city[i] == INF)
				cout << -1 << endl;
			else
				cout << city[i] << endl;
		}
	}

	return 0;
}

후기

오버플로우를 의식못하는 기초적인 실수로 약 30분 공중에 날렸다.ㅎ
기본이 중요하다는걸 다시한번 깨닫는 문제였다.