Летен камп
Како што веројатно веќе знаете, оваа година, Здружението на информатичарите на Македонија планира да организира летен камп по информатика за учениците од основните и средните училишта од државата. Кампот ќе биде организиран во некое од најатрактивните туристички места во Македонија.
Се разбира, за да е кампот што поуспешен и за да се пријават што е можно повеќе ученици, Здружението треба да организира презентации во повеќе градови од државата. Ваша задача е да напишете програма која што, за дадена листа од сите градови во државата, патишта помеѓу нив, град од кој тргнува тимот кој ќе ги одржува презентациите (почетна локација) и листа на градови кои што тимот треба да ги посети, ќе пресмета и отпечати кој е најкраткиот пат кој што тргнува од почетната локација, ги посетува сите потребни градови и се враќа на почетната локација.
Влез
Во првата линија се запишани три цели броја N (1 <= N <= 40 000), K (1 <= К <= 15) и R (1 <= R <= 50 000), кои го означуваат вкупниот број на градови во државата, бројот на градови кои што треба да се посетат, како и бројот на патишта, соодветно. Можете да претпоставите дека патната инфраструктура е таква што постои можност да се стигне од кој било град, во кој било друг.
Во втората линија се запишани K цели броеви Ci (1<= Ci < N), кои ги означуваат градовите кои треба да се посетат. Градовите се нумерирани со броевите од 0 до N-1. Тимот кој ќе ги одржува презентациите секогаш тргнува од градот означен со број 0.
Во секоја од следните R линии се запишани по три цели броја Ai, Bi и Di (0 <= Ai, Bi < N-1, 1 <= Di <= 10 000), кои означуваат дека постои двонасочен пат помеѓу градовите Ai и Bi, со должина Di.
Забелешка: Во тест случаи кои ќе носат најмалку 40% од поените, ќе важи (1 <= K <= 5).
Излез
Отпечатете ја бараната должина на најкраткиот пат.
Ограничувања
Временско ограничување: 5 seconds
Мемориско ограничување: 64 megabytes
Примери
влез 6 4 7 2 3 4 1 0 3 1 0 1 4 3 2 3 1 5 1 3 4 10 0 2 19 2 1 2 | излез 30 |
Објаснување за првиот пример: Треба да се посетат градовите 1, 2, 3 и 4. Најкраткиот пат е 0->3->4->3->2->1->0, со вкупна должина 30.