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