Нужно перебрать все перестановки подмножества натуральных чисел от 2 до N, для каждой перестановки нужно насчитать время в пути, а потом из всех времён выбрать минимум. (Желательно не забыть про крайний случай N=1, а также про то, что маршрут заканчивается в столице.)