Разбор добавил Дмитрий Молчанов

Задача несколько отличается от стандартной - в ней вес имеют не ребра, а вершины графа. Можно решать ее двумя способами: 1) Сведем задачу к стандартной, для каждой соседней пары вершин задав 2 ребра - одно из первой вершины во вторую, с весом первой вершины, второе же - из второй вершины в первую, с весом второй вершины. Теперь просто применяем стандартный алгоритм Дейкстры и находим ответ. 2) Вместо веса ребер графа сохраняем вес вершин графа. Тогда в алгоритме Дейкстры при обходе вершин, соседних с текущей, для получения расстояния до следующей вершины прибавляем вес текущей вершины к расстоянию до нее. После применения измененного алгоритма выводим ответ на поставленную задачу.