Задача Taxi. У фірмі відбулися термінові технічні роботи, що завершилися пізно вночі. K (2≤K≤16) співробітників, котрі зазвичай користуються громадським транспортом, вимагають від менеджера доставки додому на таксі. Автомобілів таксі достатньо, щоб відправити кожного співробітника окремо. Але менеджер вважає, що то занадто дорого, бо автомобіль таксі може брати відразу кількох пасажирів (від 1 до 4), і поїздка в одному й тому самому таксі кількох людей, що живуть недалеко один від одного, обходиться значно дешевше. З іншого боку, менеджер згоден, що було б нечемно примушувати співробітників чекати надворі, поки таксі відвозить їхніх колег і повертається за ними. Тому менеджер шукає найдешевший спосіб доставити усіх співробітників за місцями проживання, при дотриманні таких умов:
- K співробітників розбивають на групи, кожна з яких містить 1, 2, 3 чи 4 людини; як розподілити людей по групам, вирішує менеджер.
- Співробітники з кожної однієї групи сідають у одне таксі.
- Таксі з усією групою відвозить додому когось одного з цієї групи, він там виходить; потім таксі з рештою групи відвозить додому когось наступного, і так доки не розвезе усіх. Порядок (кого з групи відвозити першим, кого другим, тощо) також визначає менеджер.
- Сам менеджер не є одним з K співробітників і не включається до жодної групи. Він їздить власним автомобілем, і не бажає нікого підвозити.
Фірма та місця проживання співробітників знаходяться у вершинах зваженого графа, де більшість ребер неорієнтовані (дороги з двостороннім рухом), деякі — орієнтовані (односторонні). Довжини ребер задані відразу як вартості проїзду цього ребра в таксі. Гарантовано, що граф сильно зв’язний, тобто з будь-якої вершини графа є шлях (котрий, як правило, складається з кількох послідовних ребер) до будь-якої іншої.
Вартість поїздки на таксі включає в себе не лише оплату за подолану відстань, тобто суму довжин (вартостей) пройдених ребер, а ще й плату за посадку, яка береться за кожен автомобіль (незалежно від кількості людей та відстані).
Технічні умови. Програма Taxi читає з пристрою стандартного введення перший рядок, що містить кількість вершин N (5≤N≤20000), потім кількість ребер M (N≤M≤50000); потім йдуть M рядків, кожен з яких містить по чотири числа: спочатку 1 чи 2 задає одно- чи двосторонній рух; потім два числа u, v (u≠v, 1≤v≤N, 1≤u≤N) задають, які вершини з’єднує це ребро (якщо рух односторонній, то з u до v); останнє число рядка (від 5 до 5000) — вартість проїзду в таксі по цьому ребру. Наступний рядок вхідних даних містить плату за посадку (ціле число від 500 до 50000). Наступний рядок містить номер вершини (від 1 до N), де знаходиться фірма. Наступний рядок містить кількість співробітників K (2≤K≤16). Наступний рядок є останнім і містить K чисел (від 1 до N кожне) — номери вершин, де живуть співробітники. Різні співробітники можуть жити в одній вершині, але гарантовано, що ніхто з них не живе у вершині, де розміщена фірма. Програма виводить на пристрій стандартного введення єдине число — мінімальну сумарну вартість перевезення всіх співробітників.
Приклади
|
Введення |
Виведення |
|
6 7 2 1 2 200 2 1 3 1000 2 1 4 1200 2 2 3 900 2 6 2 1300 2 6 4 200 2 4 5 100 1000 1 4 2 3 5 6 |
4500 |
|
6 7 2 1 2 200 2 1 3 1000 2 1 4 1200 2 2 3 900 2 6 2 1300 2 6 4 200 2 4 5 100 500 1 4 2 3 5 6 |
3700 |
Примітка. У першому прикладі, вартості 4500 можна досягти, коли один автомобіль таксі розвозить усіх, висаджуючи у порядку 2-й, 1-й, 4-й, 3-й. У другому, вартості 3700 можна досягти, якщо задіяти два автомобілі, один з яких везе 1-го та 2-го (висаджуючи саме в такому порядку), інший — 3-го та 4-го.