백준 13168번 내일로 여행



사용한 알고리즘 : 플로이드 와샬

문제를 제가 잘못 읽은건지... 여행 경로를 정해 준다는 조건을 몰라 초반에 많이 해맸습니다.

우선 map을 사용하여 도시의 이름들을 그냥 숫자로 생각했습니다. (map[도시이름] = 숫자)

N개의 도시 중 M개를 여행하는 경로가 주어집니다.

먼저 M개 경로를 LLL이라는 벡터에 저장해 주었습니다.

dist , railo 두 행렬을 만들어,

플로이드 와샬 3중 for구문을 돌릴때,

dist, railo 두 값을 따로 계산해 주었습니다.

이후 LLL벡터에 저장된 경로를 따라가며 경로에 따른 dist, railo 값들의 sum을 계산 후,

dist 값들의 합 vs railo값들의 합+R(내일로 구입비용) 을 비교해주면 됩니다.