Hành trình qua các trạm kiểm soát
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Mạng lưới giao thông gồm $N$ địa điểm đánh số từ $1$ đến $N$ và $M$ con đường hai chiều có trọng số. Có $K$ địa điểm đặc biệt $S_1, S_2, \dots, S_K$ (các trạm kiểm soát).
Bạn xuất phát từ địa điểm $1$, cần đi qua tất cả $K$ trạm kiểm soát (theo thứ tự tùy ý, có thể đi qua các đỉnh hoặc cạnh nhiều lần) và cuối cùng dừng lại ở địa điểm $N$.
Hãy tìm tổng độ dài đường đi ngắn nhất thỏa mãn yêu cầu, hoặc in ra -1 nếu không thể.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên $N, M, K$ ($1 \le N \le 1000$, $0 \le M \le 5000$, $0 \le K \le 12$).
- Dòng thứ hai chứa $K$ số nguyên $S_1, S_2, \dots, S_K$ ($1 \le S_i \le N$). (Nếu $K = 0$, dòng này trống).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $1 \le w \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng độ dài ngắn nhất, hoặc
-1nếu không thể.
Ví dụ
| Input | Output |
|---|---|
| 5 6 2 2 4 1 2 3 2 3 4 3 4 2 4 5 5 1 3 10 2 5 20 |
14 |
| 4 2 1 3 1 2 5 3 4 5 |
-1 |
Giới hạn
- $1 \le N \le 1000$, $0 \le M \le 5000$, $0 \le K \le 12$.
- $1 \le w \le 10^9$.
Community Discussion