Bóng Chuyền

Điểm: 6,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Một thành phố có $n$ ngã tư, được đánh số từ $1$ đến $n$ . Một số cặp ngã tư được nối với nhau bằng các con đường hai chiều có độ dài nguyên dương. Giữa một cặp ngã tư có thể có nhiều con đường khác nhau.

Tại ngã tư thứ $i$ có duy nhất một chiếc taxi. Người lái taxi này đồng ý chở khách (có thể đi qua nhiều ngã tư trung gian) đến một ngã tư khác bất kỳ với điều kiện tổng quãng đường di chuyển không vượt quá $t_{i}$ mét. Chi phí một chuyến đi bằng taxi tại ngã tư $i$ luôn cố định là $c_{i}$ đồng, không phụ thuộc vào quãng đường. Mỗi chiếc taxi chỉ được sử dụng nhiều nhất một lần, và khách chỉ có thể bắt taxi tại ngã tư nơi nó đứng.

Bạn đang ở ngã tư $x$ và cần đến ngã tư $y$ . Hãy tìm tổng chi phí nhỏ nhất để đi từ $x$ đến $y$ .

Dữ liệu vào

Dòng thứ nhất chứa hai số nguyên $n$ và $m$ — số ngã tư và số con đường.
Dòng thứ hai chứa hai số nguyên $x$ và $y$ — ngã tư xuất phát và ngã tư đích.
$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_{i}$ , $v_{i}$ , $w_{i}$ — mô tả con đường nối ngã tư $u_{i}$ và $v_{i}$ có độ dài $w_{i}$ .
$n$ dòng cuối, dòng thứ $i$ chứa hai số nguyên $t_{i}$ và $c_{i}$ — quãng đường tối đa và chi phí của taxi tại ngã tư $i$ .

Dữ liệu ra

In ra tổng chi phí nhỏ nhất để đi từ $x$ đến $y$ . Nếu không thể đi đến được, in ra $- 1$ .

Ràng buộc

$1 \leq n \leq 1000$
$0 \leq m \leq 1000$
$1 \leq x, y \leq n$
$1 \leq u_{i}, v_{i} \leq n$ , $u_{i} \neq v_{i}$
$1 \leq w_{i} \leq 10^{9}$
$1 \leq t_{i}, c_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 4 1 3 1 2 3 1 4 1 2 4 1 2 3 5 2 7 7 2 1 2 7 7	9	Đi taxi từ ngã tư $1$ tới ngã tư $2$ (qua ngã tư $4$ , quãng đường $1 + 1 = 2 \leq 7$ ), chi phí $7$ . Sau đó đi taxi từ $2$ tới $3$ (quãng đường $5 \leq 7$ ), chi phí $2$ . Tổng chi phí là $9$ .
2 1 1 2 1 2 1 1 999999998 1 999999998	999999998	Taxi tại ngã tư $1$ có thể đi quãng đường $1$ vừa đủ tới ngã tư $2$ , chi phí $999999998$ .
1 0 1 1 74 47	0	Đã ở đúng ngã tư đích, không cần đi taxi.

Bình luận

Không có bình luận tại thời điểm này.