시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 162 | 57 | 45 | 38.793% |
서로 다른 도시에 사는 친구들이 급히 약속장소를 정하려고 한다. 하지만 길이 너무 복잡하고 서로 멀리 살아서, 어느 정도 시간 여유를 잡아야 할지 알아내기가 어렵다. 친구들이 한 곳에서 만나는 데 걸리는 최소한의 시간은 얼마인가?
약속장소를 잡기 위해 펼친 지도에는 도시와 각 도시를 잇는 도로에 대한 정보가 있다. 이것은 두 도시를 연결하는 길을 의미하는 것이 아니라, 연속된 길들의 집합으로서 여러 도시를 지나간다.
더욱 자세히 말하면, 각각의 T 개의 테스트 케이스에 대해 다음과 같은 것이 주어진다.
각 도시는 순서대로 1부터 N까지의 번호가 붙여져 있다.
또한, 1부터 P까지의 번호가 붙여져 있는 각 친구 i에 대해, 다음과 같은 것이 주어진다.
각 도시를 잇는 도로 j에 대해서는 다음과 같은 것이 주어진다. 도로는 단순히 두 도시를 잇는 길이 아니라, 여러 도시를 순서대로 잇는 연속된 길의 모임이다.
위의 정보들을 이용해서, 동시에 출발한 친구들이 한 도시에서 만나는 데 필요한 최소한의 시간을 구하시오. 만약 다들 모일 수 있는 도시가 없다면 '-1'을 대신 출력하시오.
모임은 도시에서만 이루어질 수 있으며, 먼저 도착한 친구들은 다른 친구들을 기다릴 수 있다.
두 도시를 바로 연결하는 도로는 둘 이상 존재할 수 없으며, 어떤 도시에 도착하였을 때, 해당 도시를 지나는 도로 간의 이동은 추가 시간 없이 자유로이 할 수 있다.
입력은 다음과 같은 형식으로 주어진다.
T
N P M
X1 V1
X2 V2
...
XP VP
D1 L1 C1,1 C1,2 ... C1,L1
D2 L2 C2,1 C2,2 ... C2,L2
...
DM LM CM,1 CM,2 ... CM,LM
N' P' M'
....
각각의 테스트 케이스에 대해서, x가 1번부터 시작하는 케이스 번호라고 하고 y가 각 케이스에 해당하는 답이라고 할 때 출력 파일의 각 줄에 "Case #x: y"와 같은 형식으로 출력한다. 친구들이 한 도시에서 만나는 것이 불가능하다면, 최소 시간 대신 '-1'을 출력한다.
3 2 2 1 1 1 2 2 1 2 1 2 5 2 2 1 1 5 100 1 3 1 2 3 2 3 4 2 5 5 2 2 1 1 5 5 1 2 1 2 1 3 3 4 5
Case #1: 1 Case #2: 3 Case #3: -1
Contest > Google > Google's Coding Competitions > Google Code Jam Korea 2012 > Code Jam Korea 2012 예선 라운드 C2번