가장 멋진 스키 코스
면접 대비시간 제한2초메모리 제한512 MB
경사로와 조건 값을 가진 DAG가 주어질 때, 내리막 경로를 따라 조건 값 합의 최댓값을 구한다.
문제
John은 겨울을 좋아한다. 스키 시즌이 되면 친구들과 함께 헬리콥터를 타고 알프스의 아무 산이나 곧바로 날아가는 헬리스키를 즐긴다. 그곳에서 눈이 쌓인 아름다운 슬로프를 따라 내려간다.
당연히 가장 좋은 눈과 가장 좋은 날씨에서만 스키를 타고 싶어 한다. 이를 위해 이들은 여러 조건을 종합한 지표를 사용하며, 주어진 날에 대해 모든 슬로프의 상태를 평가한다.
이들이 가장 멋진 코스를 찾도록 도와줄 수 있는가?
입력
입력은 다음과 같다.
- 두 정수 n (2 ≤ n ≤ 1000)과 m (1 ≤ m ≤ 5000)이 있는 한 줄. n은 슬로프 사이의 연결 지점 개수(1부터 시작하는 번호)이고, m은 슬로프 개수이다.
- m개의 줄. 각 줄에는 세 정수 s, t, c (1 ≤ s, t ≤ n, 1 ≤ c ≤ 100)가 있으며, 이는 지점 s에서 지점 t로 가는 슬로프의 상태 지표가 c임을 나타낸다.
들어오는 슬로프가 없는 지점은 경치가 좋은 산봉우리이고, 나가는 슬로프가 없는 지점은 계곡이다. 헬리콥터는 모든 연결 지점에 착륙할 수 있으므로, 친구들은 원하는 어느 지점에서든 투어를 시작하고 끝낼 수 있다. 모든 슬로프는 내리막이므로, 어디서 시작하든 슬로프를 따라 이동한 뒤에는 같은 지점에 다시 도달할 수 없다.
출력
친구들이 택할 수 있는 경로를 따라 상태 지표의 합이 가질 수 있는 최댓값을 한 수로 출력한다.
힌트
그림 C.1: 두 번째 예제의 지도