Это была  тема на минимальный остов.Все алгоритмы по нему известны. Что там оптимальнее  придумаешь?на информатикс.мск.ру задача на питоне по времени проходила.А на том ЛОШ, где ее нужно было сдать - не проходила.  Но там ограничения по времени были раз в 10 жестче.