Самый дешевый путь

@4343H · Регистрация: 08.04.2019

Студворк — интернет-сервис помощи студентам

Вам надо попасть из города N в город M.
У Вас есть csv-файл, содержащий информацию о стоимости проезда между различными парами городов на такси в виде: «город-отправления;город назначения;цена».

Определите самый дешевый путь из заданного города в другой максимум с одной пересадкой.

Гарантируется, что такой путь существует в единственном варианте.

Вот код:

Python
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
52
53
54
from csv import reader as r
 
 
def deikstra(sxema, start):
    shortest_path = {point: float('+inf') for point in sxema}
    shortest_path[start] = 0
    queue = [start]
 
    while queue:
        current = queue.pop(0)
        for neighbour in sxema[current]:
            offering_shortest_path = shortest_path[current] + sxema[current][neighbour]
            if offering_shortest_path < shortest_path[neighbour]:
                shortest_path[neighbour] = offering_shortest_path
                queue.append(neighbour)
    return shortest_path
 
 
def find_path(sxema, shortest_path, interesting_point, start_point):
    interesting_path = [interesting_point]
    current_point = interesting_point
 
    while current_point != start_point:
        [interesting_path.append(neigh) for neigh in sxema[current_point] if
         (shortest_path[current_point] - shortest_path[neigh]) ** 2 ==
         (sxema[current_point][neigh]) ** 2]
 
        current_point = interesting_path[-1]
    return interesting_path
 
 
with open('input.csv', encoding='utf-8') as file:
    reader = r(file, delimiter=';', quotechar='"')
 
    sxema = {}
 
    for i in reader:
        if '' not in i:
            a, b, weight = i
            distance = float(weight)
            if a not in sxema:
                sxema[a] = {b: distance}
            else:
                sxema[a][b] = distance
            if b not in sxema:
                sxema[b] = {a: distance}
            else:
                sxema[b][a] = distance
        else:
            start_point, this_point = i[0], i[1]
 
    shortest_path = deikstra(sxema, start_point)
    interesting_path = find_path(sxema, shortest_path, this_point, start_point)
    print(*reversed(interesting_path))

Не проходит тест, показанный на картинке. Заранее спасибо.

@4343H · 06.01.2020, 21:59 **[ТС]**

Код не тот:

Python
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
from csv import reader as r
 
 
def deikstra(sxema, start):
    shortest_path = {point: float('+inf') for point in sxema}
    shortest_path[start] = 0
    queue = [start]
    while queue:
        current = queue.pop(0)
        for neighbour in sxema[current]:
            offering_shortest_path = shortest_path[current] + sxema[current][neighbour]
            if offering_shortest_path < shortest_path[neighbour]:
                shortest_path[neighbour] = offering_shortest_path
                queue.append(neighbour)
    return shortest_path
 
 
def find_path(sxema, shortest_path, interesting_point, start_point):
    interesting_path = [interesting_point]
    current_point = interesting_point
 
    while current_point != start_point:
        [interesting_path.append(neigh) for neigh in sxema[current_point] if
         shortest_path[current_point] - shortest_path[neigh] == sxema[current_point][neigh]]
 
        current_point = interesting_path[-1]
    return interesting_path
 
 
with open('input.csv', encoding='utf-8') as file:
    reader = r(file, delimiter=';', quotechar='"')
 
    sxema = {}
 
    for i in reader:
        if '' not in i:
            a, b, weight = i
            distance = float(weight)
            if a not in sxema:
                sxema[a] = {b: distance}
            else:
                sxema[a][b] = distance
            if b not in sxema:
                sxema[b] = {a: distance}
            else:
                sxema[b][a] = distance
        else:
            start_point, this_point = i[0], i[1]
    shortest_path = deikstra(sxema, start_point)
    interesting_path = find_path(sxema, shortest_path, this_point, start_point)
    print(*reversed(interesting_path))

@geargoose · 26.10.2020, 15:12

Сложно...

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

@geargoose 67 / 64 / 3 Регистрация: 02.11.2019 Сообщений: 227
	26.10.2020, 15:12
	Сложно... 0

Опции темы