Informatica Online Judge

  주유소 #5 [1821 / 071D]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 20   Total Tried : 21


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

[KOI2017_H_2]

Background

어떤 나라에는 N개의 도시가 있고, 각 도시는 1번부터 N번까지 번호가 붙어 있다.

또, 서로 다 른 두 도시를 양방향으로 직접 연결하는 M개의 도로가 있다.

도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

1번 도시에서 N번 도시로 자동차를 이용하여 이동하려고 한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다.

기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다.

도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다.

각 도시에는 단 하나의 주유소가 있으며, 도시마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시와 4개의 도로가 있다고 하자.

원 안에 있는 숫자는 도시의 번호, 원 옆에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 옆에 있는 숫자는 도로의 길이를 표시한 것이다.



1번 도시에서 출발할 때 7리터의 기름을 넣고 그 기름으로 4번 도시까지 (3번 도시를 거쳐) 이동하면 총 비용은 35원이다.

만약 1번 도시에서 출발 할 때 3리터의 기름을 넣고(3×5=15원) 3번 도시로 이동한 다음, 다시 3번 도시에서 4리터의 기름을 넣고(4×4=16원) 4번 도시에 도착하면 총 비용은 31원이다.

또 다른 방법으로 1번 도시 에서 2리터의 기름을 넣고(2×5=10원) 2번 도시로 이동하여, 2번 도시에서 9리터의 기름을 넣고(9×2=18원) 1번과 3번 도시를 거쳐 4번 도시에 도착하면 총 비용은 28원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도로들 의 길이를 입력으로 받아 1번 도시에서 N번 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

Input

첫 번째 줄 에는 도시의 수와 도로의 수를 나타내는 정수 N (1≤N≤2,500)과 정수 M(1≤M≤4,000) 이 주어진다.

다음 줄에 각 도시 주유소의 리터당 가격이 도시 번호 순서대로 N개의 자연수로 주어진다. 리터당 가격은 1이상 2,500이하의 자연수이다.

그 다음 M개의 줄 각각에 하나의 도로 에 대한 정보가 세 개의 자연수로 주어지는데, 처음 두 개의 자연수는 도로가 연결하는 두 도시의 번호이며, 세 번째 자연수는 도로의 길이이다. 도로의 길이는 1 이상 2,500이하의 자연수이다.

한 쌍의 도시를 연결하는 도로는 최대 하나만 존재한다. 임의의 도시에서 다른 임의의 도시로 도로들을 이용하여 이동할 수 있는 방법이 항상 존재한다.

[Sub-Task Info]
#1 : 2 <= N <= 10 (18pts)
#2 : M = N-1, 1-2, 2-3, ... N-1 - N으로 연결되어 있다. (15pts)
#3 : 모든 주유소의 가격이 리터당 1원이다. (16pts)
#4 : 2 <= N <= 500 (24pts)
#5 : 추가제한사항은 없다. (27pts)

Output

1번 도시에서 N번 도시로 가는 최소 비용을 출력한다.

IO Example

입력
4 4
5 2 4 1
3 1 3
1 2 2
4 3 4
2 4 15

출력
28

입력2
4 3
5 2 5 2
1 2 2
2 3 3
3 4 1

출력2
18

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