Informatica Online Judge

  택시 [0898 / 0382]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 13   Total Tried : 16


The Champion of this Problem (C++) : gs13068 - 0ms / 1327byte
My Best Submission (C++) : N/A

[JOI 2014 Try-out]

Background

경곽이의 나라에는 1부터 N까지 번호가 붙은 도시들로 구성되어 있으며 각 도시들은 도로로 연결되어 있다.

이 나라에는 K개의 도로가 있고, 모든 도로는 서로 다른 2개의 마을을 연결한다. 도로는 양 방향으로 이동 가능하다.

이 나라의 마을 1에 사는 경곽이는 마을 N에 사는 할머니 댁에 택시로 가기로 했다. 택시회사는 각 마을에 하나씩 있다.

그리고 각 택시는 다음과 같은 규칙을 준수한다.

- 택시회사 i의 택시는 반드시 i번 마을에서 타야한다.
- 택시회사 i의 택시의 요금은 c_i로 거리에 관계없이 일정하다.
- 택시회사 i의 택시는 승차하고부터 연속해서 최대 R_i개의 도로만 지날 수 있다.

예를 들어 R_1 = 2일 경우, 마을 1로부터 택시회사 1의 택시에 타면 최대 2개의 도로만 이동가능하다. 만약 도로를 3개 이상 이동하여 가야할 마을에 가려면 적어도 1번 이상은 택시를 갈아타야 한다.

경곽이가 마을 1부터 N까지 가기위하여 필요한 요금의 최소값을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에는 마을의 수 N과 도로의 수 K가 공백으로 구분되어 입력된다.

두 번째 줄부터 N줄에 걸쳐서 각 마을의 택시회사의 요금 C_i와 최대 이동 길의 수 R_i가 공백으로 구분되어 입력된다.

다음 줄부터 K줄에 걸쳐서 서로 다른 2개의 정수 A_j, B_j가 공백으로 구분되어 입력된다. 이는 j번째 도로는 마을 A와 B를 연결한다는 의미이다.

[입력값의 정의역]
2 <= N <= 5,000
N-1 <= K <= 10,000
1 <= C_i <= 10,000
1 <= R_i <= N

Output

목적지에 도달하는데 드는 최소비용을 출력한다.

IO Example

입력
6 6
400 2
200 1
600 3
1000 1
300 5
700 4
1 2
2 3
3 6
4 6
1 5
2 4

출력
700

[설명]

마을의 구성

3---6
| |
5---1---2---4

각 번호는 마을의 번호이고, 연결된 선은 도로를 나타낸다.
테스트 케이스의 경우에 1에서 6으로 가장 싼 가격에 가기 위해서는

- 마을1에서 택시를 타고 마을5로 간다. (400사용)
- 마을5에서 택시를 타고 마을6으로 간다. (300사용)

따라서 700으로 이동가능하다. 이 보다 더 적은 가격으로 갈 수 있는 방법은 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]