- Описание
- Отправленные решения
359. Путешествие
В стране $N$ городов, пронумерованных от $1$ до $N$, соединены $M$ двунаправленными дорогами. Любая пара городов связана некоторым путём по этим дорогам, известно время путешествия по каждой дороге. У вас есть план посетить $K$ определённых городов в любом порядке, начав в городе $S$ и закончив в $F$. Найдите один из кратчайших путей.
Формат ввода
Первая строка содержит целые числа $N, M, K, S, F$ ($2 \le N \le 200; 1 \le M \le 5000; 0 \le K \le 10; 1 \le S,F \le N$) — количества городов, дорог, промежуточных городов, первый и последний города маршрута соответственно.
Следующие $M$ строк содержат описания дорог: целые числа $u_i, v_i, w_i$ ($1 \le u_i, v_i \le N; 1 \le w_i \le 10^6; u_i \ne v_i$; каждое ребро встречается на вводе не более одного раза) — города, соединяемые дорогой, и время путешествия по ней.
В последней строке через пробел перечислены $K$ промежуточных городов $c_j$ ($1 \le c_j \le N; c_j \ne S; c_j \ne F$). Все они различны.
Формат вывода
В первой строке выведите время прохождения построенного маршрута.
Во второй строке выведите все $K+2$ города этого маршрута через пробел. Маршрут обязан быть кратчайшим, при существовании нескольких ответов разрешается вывести любой.
Ограничения
Ограничение времени
1 с
Ограничение памяти
256 МБ
Пример 1
2 1 0 1 2
1 2 3
3
1 2
Пример 2
5 7 2 4 3
2 1 7
4 2 4
3 5 2
4 3 1
2 5 6
5 1 1
3 1 4
5 1
7
4 1 5 3