Задача с сайта e-olymp.com.
Условие задачи
В стране n городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в n-ый, потратив как можно меньшее количество денег.
Входные данные
Сначала идет количество городов n (1 ≤ n ≤ 100), затем идет n чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Затем идет количество дорог m в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами — номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.
Выходные данные
Выведите одно число — суммарную стоимость маршрута или -1, если добраться невозможно.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 4 1 10 2 15 4 1 2 1 3 4 2 4 3 |
3 |
| 2 | 4 1 10 2 15 0 |
-1 |
| 3 | 5 1 2 3 4 5 4 1 2 2 3 3 4 4 5 |
10 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
import java.util.*; class Main { //Условная бесконечность public static final int INF = 1000000; public static void main (String[] args) { Scanner input = new Scanner(System.in); int n, m, curFrom, curTo; n = input.nextInt(); int price[] = new int[n+1]; //Цены на бензин в i-ом городе int distance[] = new int[n+1]; //Минимальные затраты на то, чтобы обраться до i-го города boolean used[] = new boolean[n+1]; //Был ли рассмотрен этот город? Vector <Integer> graph[] = new Vector[n+1]; for (int i = 1; i <= n; ++i) { price[i] = input.nextInt(); distance[i] = INF; used[i] = false; graph[i] = new Vector(); } //Заполнение списка смежности m = input.nextInt(); for (int i = 0; i < m; ++i) { curFrom = input.nextInt(); curTo = input.nextInt(); graph[curFrom].add(curTo); graph[curTo].add(curFrom); } //Нахождение оптимальной стоимости маршрута. На каждой итерации цикла находим город, //стоимость маршрута из начального города к которому минимальна. Если оказывается, //что эта стоимость бесконечна, значит, искомого пути не существует. distance[1] = 0; for(int i = 0; i < n; ++i) { int curCity = -1; //Город, рассматривыемый в данной итерации for (int j = 1; j <= n; ++j) if (!used[j] && (curCity == -1 || distance[j] < distance[curCity])) curCity = j; if (distance[curCity] == INF) break; used[curCity] = true; //Релаксация стоимости маршрута для всех городов, в которые можно попасти из данного for(int j = 0; j < graph[curCity].size(); ++j) { int to = graph[curCity].elementAt(j); distance[to] = Math.min(distance[to], distance[curCity] + price[curCity]); } } //Вывод ответа System.out.print(distance[n] == INF ? -1 : distance[n]); } } |
Описание
Оптимальную стоимость маршрута будем находить по алгоритму Дейкстры. Цены на бензин в i-ом городе хранятся в массиве price. Минимальные стоимости маршрутов к каждому из городов хранятся в массиве distance, изначально все маршруты принимаем бесконечно дорогими. Кроме того, для хранения информации о том, был ли рассмотрен i-й город, используется массив used. Сам граф представляется в виде списка смежности. Для этого используется массив векторов <strong>graph</strong>. Если в итоге стоимость маршрута до целевого города осталась бесконечной, значит, пути к нему не существует, и выводится -1. Иначе выводится эта стоимость.
Код на ideone.com.
Засчитанное решение на e-olymp.com.