Chọn Vị Trí Trang Trại

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ thị trấn được kết nối bởi $M$ con đường hai chiều. Trong số đó có $K$ thị trấn có chợ. Một nông dân muốn xây trang trại tại một thị trấn không có chợ. Mỗi ngày, ông xuất phát từ trang trại, ghé thăm tất cả $K$ chợ theo thứ tự tối ưu, rồi trở về trang trại.

Tìm tổng quãng đường nhỏ nhất mà nông dân phải đi mỗi ngày, xét trên tất cả các vị trí trang trại có thể.

Dữ liệu vào

Dòng 1: Ba số nguyên $N$ , $M$ , $K$
$K$ dòng tiếp theo: Chỉ số của thị trấn có chợ
$M$ dòng tiếp theo: Ba số nguyên $u$ , $v$ , $w$ — con đường nối $u$ và $v$ với độ dài $w$

Dữ liệu ra

Một số nguyên — quãng đường nhỏ nhất.

Ràng buộc

$1 \leq N \leq 10000$
$1 \leq M \leq 50000$
$1 \leq K \leq 5$
$1 \leq w \leq 1000$

Ví dụ

Input	Output	Giải thích
5 6 3 1 2 3 1 2 1 1 5 2 3 2 3 3 4 5 4 2 7 4 5 10	12	Đặt trang trại tại thị trấn 5, đi theo thứ tự 1→2→3: 2+1+3+6=12

Bình luận

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