#2918

Числа-подстроки

Темы: [Алгоритм Дейкстры]

За один шаг к числу X разрешается прибавить или из числа X разрешается вычесть любое положительное число Y, десятичная запись которого является подстрокой десятичной записи числа X. Стоимость такой операции равна сумме цифр числа Y.

Необходимо за минимальную стоимость получить из числа a число b, при этом все промежуточные числа должны быть положительными и не должны превышать n.

Входные данные

Входной файл содержит три целых числа: n, a, b (1 ≤ a, b ≤ n ≤ 5000).

Выходные данные

Если из числа a нельзя получить число b, выведите в выходной файл одно число -1.

Если такая последовательность преобразований существует, в первой строке выходного файла выведите минимальную стоимость требуемого преобразования. Во второй строке выходного файла выведите число k — количество шагов в преобразовании. В последующих k строках выведите сами шаги преобразования по одному в строке. Каждая строка должна иметь вид +число или –число, в зависимости от того, прибавляется или вычитается очередное число.

Примеры

Входные данные

20 12 18

Выходные данные

5
3
-2
+10
-2

Входные данные

100 5 43

Выходные данные

29
8
+5
+1
+1
+1
+13
+26
-5
-4

Входные данные

50 5 43

Выходные данные

-1

#3345

Проложи дорогу (BC)

Темы: [Алгоритм Дейкстры]

Правительство некоторой всем известной страны решило глобально перестроить дорожную систему – оно уже успело разрушить все дороги, и теперь нужно выстроить дорожную сеть заново. Новые двусторонние дороги можно строить между любыми двумя городами, и стоимость постройки дороги равна расстоянию между соответствующими городами (здесь понимается расстояние между точками на плоскости). Однако в некоторых случаях ландшафт вынуждает построить дорогу за другую цену, такие пары городов называются особыми. Правительство решило первым делом соединить два главных города данной страны – А и Б. Вам поручили разработать план постройки дорог, при котором суммарная стоимость всех построенных дорог будет минимально возможной, и при этом по построенным дорогам можно будет добраться из города А в город Б.

Входные данные

Первая строка содержит число $N$ – количество городов в стране ($1 \leq N \leq 10^4$). Каждая из последующих $N$ строк содержит по два целых числа, $x_i$ и $y_i$ – координаты соответствующего города ($|x_i|, |y_i| \leq 10^6$). Далее содержится число $M$ – количество особых пар городов ($0 \leq M \leq min(10^4, N(N-1)/2)$). Далее в $M$ строках содержится описание особых дорог, каждое состоит из трех целых чисел: $u$, $v$ – пара различных городов, между которыми проходит особая дорога, и $w$ – стоимости постройки соответствующей дороги ($1 \leq u, v \leq N$, $0 \leq w \leq 10^6$). В последней строке содержатся номера городов А и Б (от 1 до $N$).

Выходные данные

Выведите одно число – искомую минимальную длину. Ваш ответ должен отличаться от правильного не более чем на $10^{-5}$.

Примеры

Входные данные

Выходные данные

2.0000000000

#3347

Кратчайший путь (AB)

Темы: [Куча] [Алгоритм Дейкстры]

Вам дано описание дорожной сети страны. Ваша задача – найти длину кратчайшего пути между городами А и B.

Входные данные

Сеть дорог задана во входном файле следующим образом: первая строка содержит числа $N$ и $K$ ($1 \leq N \leq 100000$, $0 \leq K \leq 300000$), где $K$ – количество дорог. Каждая из следующих $K$ строк содержит описание дороги с двусторонним движением – три целых числа $a_i$, $b_i$ и $l_i$ ($1 \leq a_i,b_i \leq N$, $1 \leq l_i \leq 10^6$). Это означает, что имеется дорога длины $l_i$, которая ведет из города $a_i$ в город $b_i$. В последней строке находятся два числа $А$ и $В$ – номера городов, между которыми надо посчитать кратчайшее расстояние ($1 \leq A, B \leq N$)

Выходные данные

Вы должны вывести в выходной файл единственное число – расстояние между требуемыми городами. Если по дорогам от города $А$ до города $В$ доехать невозможно, выведите –1.

Примеры

Входные данные

Выходные данные

#3494

Алгоритм Дейкстры за $M$~log$N$

Темы: [Алгоритм Дейкстры] [Куча]

Напишите программу, которая будет находить расстояния в неориентированном взвешенном графе с неотрицательными длинами ребер, от указанной вершины до всех остальных. Программа должна работать быстро для больших разреженных графов.

Входные данные

В первой строке входных данных задано число NUM — количество различных запусков алгоритма Дейкстры (на разных графах). Далее следуют NUM блоков, каждый из которых имеет следующую структуру.

Первая строка блока содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них в пределах от 0 до N–1 каждое и обозначают концы соответствующего ребра, третье — в пределах от 0 до 20000 и обозначает длину этого ребра. Далее, в последней строке блока, записанное единственное число от 0 до N–1 — вершина, расстояния от которой надо искать.

Количество различных графов в одном тесте NUM не превышает 5. Количество вершин не превышает 60000, рёбер — 200000.

Выходные данные

Выведите на стандартный выход (экран) NUM строк, в каждой из которых по N_i чисел, разделенных пробелами — расстояния от указанной начальной вершины взвешенного неориентированного графа до его 0-й, 1-й, 2-й и т. д. вершин (допускается лишний пробел после последнего числа). Если некоторая вершина недостижима от указанной начальной, вместо расстояния выводите число 2009000999 (гарантировано, что все реальные расстояния меньше).

Примеры

Входные данные

Выходные данные

18 0 5 2 8

#111526

Большая прогулка

Темы: [Алгоритм Дейкстры]

Во время летних каникул Вася и Петя путешествовали со своими родителями по Одной Очень Гостеприимной Стране. В этой стране всего N городов, пронумерованных числами от 1 до N. Маршрут Васи начинался в городе A и заканчивался в городе B, а маршрут Пети – начинался в городе C и заканчивался в городе D. Поскольку времени у них было немного, то и Васины и Петины родители выбрали самый короткий путь, соединяющий начальный и конечный города их маршрута.

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

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

Обратите внимание на то, что поскольку на некоторых дорогах шел ремонт, то длина пути от города X в город Y может отличаться от длины пути от города Y в город X.

Входные данные

В первой строке вводится число N (1 ≤ N ≤ 100). В следующих N строках вводится по N чисел, не превосходящих 100, j-ое число в i-ой строке равно длине пути между i-м и j-м городом. Известно, что между любыми двумя городами есть дорога и поскольку на некоторых дорогах идет ремонт, то длина пути от города X в город Y может отличаться от длины пути от города Y в город X. В следующих двух строках вводятся пары целых числа от 1 до 100 – номера городов, являющихся началом и концом маршрута Васи (A и B), и аналогичные числа для Пети (C и D).

Выходные данные

Выведите их номера в порядке возрастания. Если маршруты ребят не пересекались, выведите одно число - 1. Гарантируется, что кратчайший путь – единственный.

Примеры тестов

Входные данные

4
0 100 100 1
100 0 3 100
100 4 0 1
100 3 10 0
1 3
2 3

Выходные данные

2 3