백준 11657번 타임머신

문제 링크입니다: www.acmicpc.net/problem/11657

11657번: 타임머신

N: 도시의 개수 -> 범위: 1 <= N <= 500

M: 버스노선의 개수 -> 범위: 1 <= M <= 6,000

A, B: 시작, 도착 도시 -> 범위: 1<= A, B <= N

C: 버스 타고 이동하는 시간 -> 범위: -10,000 <= C <= 10,000

dist: 1번 노선부터의 거리를 저장하는 배열

City 구조체: A, B, C를 변수로 갖는 구조체 (내가 왜 이렇게 구조체명을 지었는지는 이해가 안 간다...)

cities: 버스 노선 정보를 입력받는 구조체 배열

 

알고리즘

1. 버스 노선 정보를 입력 받고 dist 배열 INF로 초기화

2. 벨만포드 알고리즘 진행하며 dist 배열 업데이트

2.1 dist[ROOT] = 0 => ROOT에서 ROOT까지의 거리는 0이므로

2.2 1 ~ N 도시들을 반복문 돌리고 버스 노선들을 대상으로 이차 반복문을 돌리며 dist 업데이트 (즉, A + C가 B 비용보다 작을 때 B 업데이트)

2.3 N번째 도시까지 dist[B] 계속 업데이트한다면 무한 사이클로 판단 (INF가 상당히 큰 값이기 때문에 dist 배열 자료형을 long long으로 해주는 것이 핵심)

3. 결과 출력 후 프로그램 종료

 

* 벨만포드 알고리즘을 적용한 이유: 간선의 가중치가 음수가 주어질 수 있기 때문에!

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	const int ROOT = 1;
	const int MAX = 500 + 50;
	const int BUS_MAX = 6000 + 60;
	const int INF = 987654321;
	typedef struct
	{
	int A, B, C;
	}City;
	int N, M;
	long long dist[MAX];
	City cities[BUS_MAX];
	void init(void)
	{
	for (int i = 0; i < MAX; i++)
	{
	dist[i] = INF;
	}
	}
	// BellmanFord
	void printDistance(void)
	{
	bool cycle = false;
	dist[ROOT] = 0;
	for (int n = 1; n <= N; n++)
	{
	for (int m = 0; m < M; m++)
	{
	int A = cities[m].A;
	int B = cities[m].B;
	int C = cities[m].C;
	if (dist[A] == INF)
	{
	continue;
	}
	if (dist[B] <= dist[A] + C)
	{
	continue;
	}
	dist[B] = dist[A] + C;
	if (n == N)
	{
	cycle = true;
	}
	}
	}
	if (cycle)
	{
	cout << -1 << "\n";
	return;
	}
	for (int n = 2; n <= N; n++)
	{
	if (dist[n] == INF)
	{
	cout << -1 << "\n";
	continue;
	}
	cout << dist[n] << "\n";
	}
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int m = 0; m < M; m++)
	{
	City temp;
	cin >> temp.A >> temp.B >> temp.C;
	cities[m] = temp;
	}
	init();
	printDistance();
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~