UniLecs #116_1. Вагонетка
UniLecsЗадача: В одной области одной северной страны, где нет нормальных дорог, чтобы добраться из одного поселка до другого люди вынуждены пользоваться самодельной вагонеткой для доставки грузов. В этой области N поселков и только нектр из них соединены между собой старой железной дорогой. Для проезда по ней из одного поселка до другого нужна одна канистра горючего, но в каждом поселке своя стоимость канистры горючего. А вагонетка слишком мала, и вы не можете взять с собой доп.канистры. Необходимо довести груз из 1го поселка до N-го, при этом использовать минимальное кол-во средств на горючку.
Входные данные: OilCosts = [oilCost_1, oilCost_2, ... oilCost_N] - массив, где oilCost(i) - стоимость канистры горючего в i-м поселке.
TrainRoads = [ (Ai, Bj) ] - массив, где (Ai, Bj) - железная дорога, ктр соединяет поселок Ai c поселком Bj.
Дороги двухсторонние, и разумеется, между любыми двумя поселками не более 1 одной дороги.
Вывод: вывести оптимальный маршрут, т.е. номера поселков на этом маршруте.
Пример:
OilCosts = [5, 10, 1]
TrainRoads = [ (1, 3), (1, 2), (3, 2) ]
Answer: 1 -> 3
Реализация:
- @lPestl, R, C#: 1.1 балл
R:
https://gist.github.com/lpestl/132711523428e6aa547a2216e800f124
C#:
https://gist.github.com/lpestl/fe937f0866995c9e2c03a26b9571da5e
2. @akolosov364, JS: 1 балл
https://gist.github.com/KolosovAO/668dfd7d0f9a43f99d8b300de90548d5
3. @LostInKadath, С++: 1 балл.
"Given a non-oriented graph. Its edges are not weighed, but each vertice has a cost.Find a path of minimum cost from the first to the last vertice.This solution is implemented in the spirit of a good old Diixtra algorithm.The graph is transformed to a weighed oriented graph using this rule:- if a vertice has a cost of C, so its outgoing edges will have a weight of C;- if a vertice A (of cost CA) and a vertice B( of cost CB) are connected with an edge, so the edge A-B will have a weight of CA, and the edge B-A will have a weight of CB.And now we can use Diixtra.The code is detailed, self-documented, has some non-optimized things, duck tapes... as usual. =)"
https://gist.github.com/LostInKadath/953065785190734dc399dfff51e0bb95
4. @tvolf, PHP: 1 балл.
Для решения задачи используем классический алгоритм Дейкстры для нахождениякратчайшего пути. Ребро, связывающее две вершины, будет иметь два весовых значения,отличающиеся для направления в одну и другую сторону. Таким образом, матрица смежностибудет несимметрична относительно главной диагонали.
https://gist.github.com/tvolf/b5d4deef754fc938555a4e13288a7480
5. @Zernov_A, Java: 2 балла за 3 варианта решения с помощью Алгоритмов Дейкстры, Беллмана — Форда и Флойда — Уоршелла. Круто!
И отдельно 0.5 балла за крутую реализацию на SQL!!! Итого: 2.5 балла! Браво!
Задача решена 3-мя способами, с помощью классических алгоритмов поиска кратчайшего пути: Алгоритм Дейкстры; Алгоритм Беллмана — Форда; Алгоритм Флойда — Уоршелла
В качестве графа мы рассмотрим поселки и дороги между ними. Данный граф является взвешенным и ориентированным. Вес ребра, соединяющего вершины i->j будет равен OilCosts[i] (стоимости канистры горючего в i-м поселке)
https://github.com/AlexZDeveloper/TrolleyRoute
SQL:
http://rextester.com/YLAH33423
Test:
https://repl.it/@AlexZDeveloper/TrolleyRoute
6. @dbond762, Python, Rust: 1.1 балла. Подробный разбор и комментарии к коду смотри в gist-файле
https://gist.github.com/dbond762/2b1d3562ffa9d5d093b9f0e6a6296046
Test Python:
https://repl.it/repls/WillingAptShell
Test Rust:
7. @kirillmotrichkin, Python: 1 балл.
https://gist.github.com/superkiria/4f1de0e558c4e5e7f8aaa4ddcf279f2a
Test:
https://repl.it/@superkiria/unilecs116train
8. Антон, Rust: 1 балл
https://gist.github.com/AnthonyMikh/1ad4f756ba0e6152bcab5b7b5b064626
Test:
http://play.rust-lang.org/?gist=8e27441b2a7438ba590f9dfdf9c076d7
9. @egormasharskii, C++: 2.5 балла
3 реализации : Bellman-Ford "в лоб"; Bellman-Ford с небольшой оптимизацией по поводу остановки; Дейкстра в варианте с медленной очередью с приоритетами; Дейкстра в варианте с очередью с логарифмическим обновлением веса
https://gist.github.com/myegor/95f495607e749af6e8e4ddbfd817e911
10. @jinxonik, Python: 1 балл. Евгений расслабился, всего лишь одна реализация :)
Алгоритм Форда-Беллмана. Находит расстояние от одной вершины до всех остальных за количество операций порядка n*m. Заведём массив d[1..n], в котором на i-ой итерации будем хранить общую стоимость движения до посёлка с ограничением на то, что в путь должно входить строго меньше i рёбер. Если таких путей до вершины j нет, то d[j] = inf (очень большая величина, в качестве которой я принял удвоенную суммарную стоимость горючего на всех станциях). В самом начале d заполнен значениями inf. Чтобы обновлять на i-ой итерации массив, надо просто пройти по каждому ребру и попробовать улучшить расстояние до вершин, которые оно соединяет. Кратчайшие пути не содержат циклов, так как все циклы неотрицательны, и мы можем убрать цикл из пути, при этом длина пути не ухудшится. Поэтому длина кратчайшего пути не больше n-1, значит, после n-ой итерации d будет содержать стоимость до нужного нам посёлка. Для нахождения маршрута заведём массив p[1..n], в котором для каждой вершины будем хранить её "предка", т.е. предпоследнюю вершину в кратчайшем пути, ведущем в неё. В самом деле, кратчайший путь до какой-то вершины a является кратчайшим путём до какой-то вершины p[a], к которому приписали в конец вершину a. Параметры: w - массив "весов" (стоимостей горючего на каждой станции), e - массив ребёр.
https://gist.github.com/jin-x/38eb69cefac997ddc92f00304533dcc5
Test:
https://repl.it/@jin_x/UniLecs-116-Trainpy
11. @ak0noplev, Python: 1 балл
https://gist.github.com/rtkn07/d2c35c0d9c8dfce3f06d3ffe0c6a73a4