지금은 1860년. 포니 익스프레스는 미국 동해안과 서해안을 연결하는 가장 빠른 우편 배송 시스템입니다. 이 시스템은 N개의 도시를 연결합니다. 각 도시마다 한 마리의 말이 있습니다 ("말 한 대로 다 둘러볼 정도의 도시"죠); 각각의 말은 특정 속도로 달리며, 지칠 때까지 달릴 수 있는 최대 거리가 정해져 있습니다.
포니 익스프레스의 기수는 시작 도시의 말로 출발합니다. 기수는 도시에 도착할 때마다 타고 온 말을 그대로 쓸 수도, 그 도시의 말로 바꿀 수도 있습니다; 교환은 즉시 이루어집니다. 말이 쉬는 시간은 없어, 말이 최대 거리의 일부를 "소진"한다면 영원히 소진한 채로 있어야 합니다. 기수가 목표 도시에 도착한다면 우편은 배송됩니다.
도시 사이 경로는 회사 소유주, 법조인, 연합 대표, 사촌 피트 사이의 복잡한 협의를 통해 결정됐습니다. 따라서 도시 간 거리는 상식과 꼭 일치하지 않습니다: 예를 들어 삼각 부등식이 꼭 성립하지도 않으며, 도시 A에서 도시 B까지 거리가 도시 B에서 도시 A까지 거리와 다를 수도 있습니다!
당신은 시간 여행 사업가로 미래에서 빠른 컴퓨터를 가지고 왔습니다. 컴퓨터 한 대로는 이메일 서비스를 설립하고 포니 익스프레스를 시대의 뒷전으로 몰아넣기는 어렵지만, 포니 익스프레스를 위해 최적 경로를 계획할 수는 있습니다. 도시 간 경로와 각 도시의 말에 대한 모든 데이터가 주어지고 시작 도시와 도착 도시 쌍 배열이 주어질 때, 각 배송마다 필요한 최소 시간을 빠르게 계산할 수 있습니까? (모든 배송은 서로 독립적입니다; 한 경로에서 도시의 말을 사용한다고 다른 경로에서 사용할 수 없게 되지는 않습니다.)
입력
첫 줄에 테스트 케이스의 수 T가 주어집니다. 이후 T개의 테스트 케이스가 주어집니다. 각 테스트 케이스는 아래와 같습니다:
한 줄에 두 정수가 주어집니다: N은 말이 있는 도시의 수를 나타내며 Q는 구하려는 경로의 수를 나타냅니다. 도시의 번호는 1부터 N까지입니다.
N개의 줄에 km 기준 i번째 도시의 말이 갈 수 있는 최대 거리 Ei와 km/h 기준 말이 달리는 속도 Si 두 정수가 주어집니다.
N개의 줄에 각각 N개의 정수가 주어집니다. i번째 줄의 j번째 정수인 Dij는 i번째 도시에서 j번째 도시로 바로 가는 경로가 없을 경우 -1이며, 그렇지 않을 경우 경로의 길이를 나타냅니다.
Q개의 줄에 각각 계산하려 하는 k번째 도시 쌍의 시작점과 도착점을 나타내는 두 정수 Uk와 Vk가 주어집니다.
제한은 아래와 같습니다.
1 <= T <= 100
2 <= N <= 100
모든 i에 대해 1 <= Ei <= 109
모든 i에 대해 1 <= Si <= 1000
모든 i, j에 대해 -1 <= Dij <= 109
모든 i에 대해 Dii = -1. (자기 자신으로 바로 가는 경로는 없다.)
모든 i, j에 대해 Dij ≠ 0.
모든 k에 대해 Uk ≠ Vk.
모든 k에 대해, Uk에서 Vk로의 배송이 주어진 말로 언제든 가능하다는 것이 보장되어 있다.
서로 다른 l, m에 대해 Ul ≠ Um 그리고/또는 Vl ≠ Vm이다. (테스트 케이스 내에서 계산하는 도시 순서 쌍이 반복되는 경우는 없다.)
1 <= Q <= 100
모든 k에 대해, 1 <= Uk <= N.
모든 k에 대해, 1 <= Vk <= N.
출력
각 테스트 케이스에 대해 x가 (1부터 시작하는) 테스트 케이스의 번호를 나타내고, yk는 Uk에서 Vk로 편지를 배송할 때 걸리는 최소 시간을 시간 단위로 나타낸 값이 되도록 Case #x: y1 y2 ... yQ를 출력합니다.
ez_code 3년 전 2
문제
지금은 1860년. 포니 익스프레스는 미국 동해안과 서해안을 연결하는 가장 빠른 우편 배송 시스템입니다. 이 시스템은 N개의 도시를 연결합니다. 각 도시마다 한 마리의 말이 있습니다 ("말 한 대로 다 둘러볼 정도의 도시"죠); 각각의 말은 특정 속도로 달리며, 지칠 때까지 달릴 수 있는 최대 거리가 정해져 있습니다.
포니 익스프레스의 기수는 시작 도시의 말로 출발합니다. 기수는 도시에 도착할 때마다 타고 온 말을 그대로 쓸 수도, 그 도시의 말로 바꿀 수도 있습니다; 교환은 즉시 이루어집니다. 말이 쉬는 시간은 없어, 말이 최대 거리의 일부를 "소진"한다면 영원히 소진한 채로 있어야 합니다. 기수가 목표 도시에 도착한다면 우편은 배송됩니다.
도시 사이 경로는 회사 소유주, 법조인, 연합 대표, 사촌 피트 사이의 복잡한 협의를 통해 결정됐습니다. 따라서 도시 간 거리는 상식과 꼭 일치하지 않습니다: 예를 들어 삼각 부등식이 꼭 성립하지도 않으며, 도시 A에서 도시 B까지 거리가 도시 B에서 도시 A까지 거리와 다를 수도 있습니다!
당신은 시간 여행 사업가로 미래에서 빠른 컴퓨터를 가지고 왔습니다. 컴퓨터 한 대로는 이메일 서비스를 설립하고 포니 익스프레스를 시대의 뒷전으로 몰아넣기는 어렵지만, 포니 익스프레스를 위해 최적 경로를 계획할 수는 있습니다. 도시 간 경로와 각 도시의 말에 대한 모든 데이터가 주어지고 시작 도시와 도착 도시 쌍 배열이 주어질 때, 각 배송마다 필요한 최소 시간을 빠르게 계산할 수 있습니까? (모든 배송은 서로 독립적입니다; 한 경로에서 도시의 말을 사용한다고 다른 경로에서 사용할 수 없게 되지는 않습니다.)
입력
첫 줄에 테스트 케이스의 수 T가 주어집니다. 이후 T개의 테스트 케이스가 주어집니다. 각 테스트 케이스는 아래와 같습니다:
제한은 아래와 같습니다.
출력
각 테스트 케이스에 대해 x가 (1부터 시작하는) 테스트 케이스의 번호를 나타내고, yk는 Uk에서 Vk로 편지를 배송할 때 걸리는 최소 시간을 시간 단위로 나타낸 값이 되도록 Case #x: y1 y2 ... yQ를 출력합니다.
각 yk는 정답과 10-6 이내의 절대 또는 상대 오차를 지녀야 정답으로 인정됩니다.