@bobiko

Здравствуйте, форумчане. Не знаю даже, как эту задачу коротко объяснить, или даже задать теги, но вот есть фотка. Помощь требуется во всей задачи, т.к. даже не могу понять алгоритм, который нужно задать.

0

magirus

задание перепечатываем на форум.

0

@bobiko

magirus, а что не так с вложением, что нужно перепечатывать?

0

magirus

правила форума, пункт 5.18.

0

@bobiko

magirus, ох, простите, все исправлю

0

@bobiko

Вот условие:

Задача С.Стажировка
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 1 секунда
Ограничение по памяти: 64Mb

Студентов частенько отправляют на различные стажировки. Наш Витя - не исключение. В ээтом году его отправили стажироваться в Карликанию. В этой стране N городов и M дорог между ними. Каждая дорога соединяет два разных города. Между любыми двумя городами не более одной дороги. Стажировка длится четыре дня.

Каждый день Витя хочет провести в новом году, а переезжать между городами он планирует ночью. Переезд между двумя городами, если между ними есть дорого, всегда занимает ровно одну ночь и стоит определенную сумму денег (для разных пар городов, возможно, разную)

В Карликани нет трёх городов, попарно соединенных дорогами (т.е. в графе дорог нет треугольников).

Помогите Вите выбрать четыре города для стажировки так, чтобы в результате он потратил как можно меньше денег на переезды.


Формат входных данных

В первой строке входного файла записаны два числа N и M - количество городов и дорог (4 ≤ N ≤ 400; M < N *(N - 1)/2 ). Далее следует M строк, в каждой по 3 числа, описывающие дороги. Первые два числа - это номера городов, которые соединяет дорога (оба от 1 до N), а третье число - цена переезда (натуральные числа от 1 до 10⁶).


Формат выходных данных

В выходной файл выведите одно число - минимальное количество денег, необходимых Вите для переездов.

Требуется помощь в ее решение, т.к. даже не могу понять нужный алгоритм

Примеры

Миниатюры

 

0