Hành trình qua các trạm kiểm soát

Buổi 24 — Mock Contest Phase 1
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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 -1 nế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$.
Draft saved