백준 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. 결과 출력 후 프로그램 종료

 

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

 

 

개발환경:Visual Studio 2017

 

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