Задача №111624. Коммивояжер
Коммивояжёр (фр. commis voyageur) – сбытовой посредник, который, перемещаясь по рынку, выполняет роль простого посредника или действует по поручению своего клиента (продавца). В капиталистическом обществе – разъездной торговый агент какой-нибудь фирмы, предлагающий покупателям товары по образцам и каталогам.
Баян – музыкальный инструмент, разновидность гармоники с полным хроматическим звукорядом на правой клавиатуре, басами и готовым аккордовым или готово-выборным аккомпанементом на левой. Назван в честь древнерусского певца-сказителя Бояна
Вам предлагается решить вариацию классической задачи, называемой задачей коммивояжёра.
Известен список городов, которые требуется посетить. Города представлены точками на плоскости, расстояние между городами определяется как обычное евклидово расстояние между точками. Требуется найти как можно более короткий маршрут, проходящий по всем городам. Заметьте, что возвращаться назад не нужно.
Задачу не обязательно решать точно. Но чем оптимальнее вы её решите, тем больше баллов получите.
В первой строке ввода записано целое число \(N\) – количество городов в маршрутном листе коммивояжёра (\(2 \le N \le 5\,000\)). Города не совпадают.
В следующих \(N\) строках записано по два целых числа – координаты городов. Все координаты не превышают \(10^9\) по абсолютному значению.
Выведите \(N\) различных целых чисел от \(1\) до \(N\) – номера городов в порядке обхода.
- \(SCORE\) – максимальное количество баллов за тест,
- \(Best\) – длина лучшего пути, найденного решением жюри или решением участника,
- \(Len\) – длина пути, предоставленного Вами.
2 -226756261 248930550 -424486189 126864055
2 1
5 -602743451 390019627 181890547 -540955102 13062715 -787708498 450426248 -230524008 679594821 354215246
3 2 4 5 1