Dijkstra算法的故障及其性能

Question

内存限制：512MB，时间限制：4s

这个算法显示，如果你的汽车油箱=k，是否有可能从v“骑”到u。若这是不可能的，那个么算法将搜索最佳的重新加注（在重新加注油箱装满之后）。但我的代码不符合时间限制。请帮我接通电源

投入：

（一排）：k-汽车油箱，n-城市数，m-城市间道路数，u-起点城市，v-终点城市

（接下来的m行）：q，p，-与道路m相连的城市数量，r-这条道路的长度

（下一行）：l-重新加注的数量

（在一行中）：重新加注的城市

输出：重新填充的最小计数

示例：

输入：3 1 2 3 1 3 4 2 3 3 2. 2 3 产出：1

输入：3 1 2 2 1 3 4 2 3 2 0 输出：-1

输入：3 1 2 2 1 3 4 2 3 1 0 输出：0

def主： 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)