문제
성이는 깃발뺏기 게임을 하고 있다.
맵에는 N개의 성이 있으며 각각 1부터 N까지의 번호가 붙어 있다. 성이는 특정 성에서 출발하여 상대방의 깃발이 있는 성으로 진입을 해야 한다. 어떤 성에서 다른 성으로 진입하는 경로는 여러 가지가 존재할 수 있는데 가능한 최소의 병사들만 이끌고 깃발이 있는 성까지 이동하려고 한다.
성과 성 사이로 이동하기 위해서 필요로 하는 병사들의 수가 M개 주어지고, T개의 코스가 주어지면 각 코스들에 대하여 필요로 하는 최소한의 병사들의 수를 구하여 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에 성의 개수 N, 단방향 경로의 개수 M, 구하고자 하는 코스의 개수 T가 각각 공백으로 구분되어 입력된다. (1 ≤ N ≤ 300, 1 ≤ M ≤ 25,000, 1 ≤ T ≤ 35,000)
다음 줄부터 M개의 줄에 걸쳐 각 줄에 경로를 나타내는 세 개의 정수 Si, Ei, Hi가 공백으로 구분되어 입력되는데 Si번 성에서 Ei번 성으로 가기 위해 필요로 하는 병사의 수가 Hi임을 나타낸다.
다음 줄부터 T개의 줄에 걸쳐 각 줄에 코스를 나타내는 두 개의 정수 Ai와 Bi가 공백으로 구분되어 입력되며 Ai에서 Bi로 진입하기 위해 필요한 최소 병사수를 구하라는 것이다.
출력
매 줄마다, 각각의 코스에 대해 필요한 병사수의 최소값을 출력한다. 만약 갈 수 있는 경로가 없다면 -1을 출력한다.
예제
5 6 3
1 2 12
3 2 8
1 3 5
2 5 3
3 4 4
2 4 8
2 5
1 2
5 1
3
8
-1
출처
2015 ICT Award KOREA
로그인해야 코드를 작성할 수 있어요.