114. Дан граф, в котором длины всех рёбер — различные целые числа. В весовой матрице указано, что кратчайший путь из вершины A до вершины K равен 33. Определите наименьшее возможное значение произведения x1 и x2.

По матрице есть путь A → C → G → H → J → K длины 15 + 8 + 6 + 3 + 1 = 33. Другой путь через D и G имеет длину x1 + x2 + 6 + 3 + 1 = x1 + x2 + 10. Чтобы кратчайший путь оставался равен 33, необходимо x1 + x2 ≥ 23.

Все веса рёбер должны быть различными положительными целыми числами. Наименьшая допустимая пара с суммой не меньше 23 — 9 и 14: меньшие варианты с одним из чисел 1, 2, 3, 4, 5, 6, 7 или 8 либо дают сумму меньше 23, либо повторяют уже имеющийся вес ребра.

При x1 = 9 и x2 = 14 путь через D имеет длину 33, а остальные пути короче 33 отсутствуют. Произведение равно 9 · 14 = 126.

Ответ: 126.