Проблема с алгоритмом Дейкстры и его производительностью - PullRequest
Новая
       19

Проблема с алгоритмом Дейкстры и его производительностью

0 голосов
/ 05 ноября 2019

Ограничение памяти: 512 МБ, ограничение по времени: 4 с

Этот алгоритм показывает, можно ли «ехать» с v на u, если бак вашего автомобиля = k. Если это невозможно, алгоритм ищет оптимальное пополнение (после заполнения бака). Но мой код не соответствует времени. Помогите мне включить его, пожалуйста

Входные данные:

(в один ряд): k - автоцистерна, n - количество городов, m - количество дорог между городами, u - началогород, v - конечный город

(следующие строки m): q, p, - количество городов, связанных с дорогой m, и r - длина этой дороги

(следующий ряд): l- количество пополнений

(в одну строку): города, в которых пополнение *

вывод: минимальное количество пополнений.

Примеры:

ввод:3 3 3 1 3 1 2 3 1 3 4 2 3 3 2 2 3 Выход: 1

вход: 3 3 3 1 3 1 2 2 1 3 4 2 3 2 0 Выход: -1

вход: 3 3 3 1 3 1 2 2 1 3 4 2 3 1 0 выход: 0

def main: k, n, m, u, v = map (int, input (). split ()) 

w = [[0] * n for i in range(n)]

for j in range(m):
    p, q, r = map(int, input().split())
    w[p - 1][q - 1] = r
    w[q - 1][p - 1] = r

if (min(w[u-1]) > k) or (min(w[v-1]) > k):
    print("-1")
    exit(0)

f = int(input())
if f > 0:
    refills = list(map(int, input().split()))

availableRefills = [0] * n


def dejkstr(source, dest):
    source -= 1
    dest -= 1
    v = 0
    visited = [False] * n
    D = [10000000000] * n

    visited[source] = True

    for i in range(n):
        if w[source][i] != 0:
            D[i] = w[source][i]
    D[source] = 0

    for i in range(n):
        minx = 10000000000
        for j in range(n):
            if (D[j] < minx) and (D[j] != 0) and (not visited[j]):
                minx = D[j]
                v = j
        for j in range(n):
            if (not visited[j]) and (D[j] > D[v] + w[v][j]) and (w[v][j] != 0):
                D[j] = D[v] + w[v][j]
        source = v
        visited[v] = True
    return D[dest]

fuelStations = 0
while (u != v) and (fuelStations < f):
    kmNeeded = dejkstr(u, v)
    if k >= kmNeeded:
        print(fuelStations)
        exit(0)
    else:
        if f == 0:
            print("-1")
            exit(0)
        else:
            j = 0
            for i in range(f):
                tarFuelCity = refills[i]
                kmNeeded = dejkstr(u, tarFuelCity)

                if (kmNeeded <= k) and (tarFuelCity != u):
                    availableRefills[j] = tarFuelCity
                    j += 1

            bestRefillKM = 10000000000
            bestRefill = 0
            for i in range(f):
                if availableRefills[i] > 0:
                    overallKM = dejkstr(u, availableRefills[i])
                    overallKM = overallKM + dejkstr(availableRefills[i], v)
                    if overallKM < bestRefillKM:
                        bestRefillKM = overallKM
                        bestRefill = availableRefills[i]

            u = bestRefill
            fuelStations += 1

            for i in range(len(availableRefills)):
                availableRefills[i] = 0

if u == v:
    print(fuelStations)
else:
    print("-1")
exit(0)
...