#849. SHIPPING - Vận chuyển hàng

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Hiện nay, với tình hình dịch COVID diễn biến phức tạp, rất nhiều người dân đã không đi mua hàng trực tiếp mà chọn cách mua hàng online, chính vì vậy mà các Shipper rất bận rộn.

Mạng lưới giao thông ở Sơn La được xem như một đồ thị có hướng gồm n đỉnh là nhà các hộ dân (đánh số từ 1 đến n ), m cung có hướng là các con đường (một chiều) nối từ nhà hộ dân này tới nhà hộ dân kia.

Có một điểm tập kết hàng của hãng SHIPPING Express đặt tại nhà dân đánh số 1 . Có k đơn hàng cần vận chuyển tới nhà các hộ dân d_1,d_2,…,d_k .

Tại mỗi thời điểm có thể vận chuyển số đơn hàng tùy ý, chi phí để vận chuyển các đơn hàng qua mỗi con đường bằng chính số lượng đơn hàng vận chuyển qua đó. Bạn hãy giúp hãng SHIPPING Express tính chi phí tối thiểu để vận chuyển hết k đơn hàng (giả thiết luôn đảm bảo vận chuyển được hết các đơn hàng).

Dữ liệu vào:

  • Dòng đầu tiên gồm ba số nguyên n,m,k\ (1≤n≤10000,0≤m≤50000,0≤k≤n) ;
  • Dòng thứ hai (nếu k>0 ) gồm k số nguyên dương d_1,d_2,…,d_k\ (1≤d_i≤n) ;
  • m dòng tiếp theo, mỗi dòng gồm hai số nguyên u,v\ (1≤u,v≤n,u≠v) với ý nghĩa có con đường một chiều nối từ nhà hộ dân u tới nhà hộ dân v .

Dữ liệu ra:

  • Ghi ra chi phí nhỏ nhất để vận chuyển hết k đơn hàng.

Ví dụ:

Dữ liệu vào:
4 3 3
2 3 4
1 3
1 2
2 4
Dữ liệu ra:
4

Giới hạn:

  • 70\% số điểm có n≤500,m≤1000 ;
  • 30\% số điểm còn lại không có ràng buộc gì thêm.