algospot 철인 n종 경기 (문제 ID: NTHLON) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/NTHLON

algospot.com :: NTHLON

입력으로 두 선수의 종목당 걸리는 시간이 주어질때 두 선수를 비기도록 코스를 설계하는것이 가능한지 판단한다.

만약 비기도록 코스를 설계 가능하다면 그 중 제일 짧은 코스는 몇분걸리는지 계산하는 문제이다.

 

해당 문제를 그래프로 표현하여 해결가능하다.

우선 두 선수의 시간차를 번호로하는 정점을 만들고 걸리는 두 선수중 한 선수를 정해 해당 선수가 걸리는 시간을 가중치로 삼는다.

맨 처음 정점도 계산을 위해 0번이어야 하고, 마지막 정점도 0번이어야 하므로 두 0번 정점을 구분하기 위해 시작점을 따로 둔다.

또한 차이의 합이 200이 넘어가는 코스는 순서를 바꿔 200이 안넘어가게 설계가능하므로 -200부터 +200범위안을 표현하는 정점들로만 계산 가능하다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/30.%20ShortestPath/NTHLON.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2