My life story

1. 문제 링크 https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1≤N≤300), M(2≤M≤N), K(1≤K≤100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1≤a, b≤N, 1≤c≤10,000)가 주어진다. 이는 a번 도시에서 b번 도시로 이동하는 항로가 있고, 서비스되는 기내식의 점수가 c점이라는 의미이다. 서쪽에서 동쪽으로 이동하는 항로가 입력될 수도 있고, 같은 도시 쌍 사이에 항로가 여러 개 있을 수도 있 www.acmicpc.net 2. 문제 개요 M개 이하의 도시를 지나는 여행을 계획하려 한다. 여행경로는 반드시 1번 도시에서 시작해서 N번 도시에서 끝..