1753最短パス

1929 ワード
テキストリンク

白準1753最短経路問題-1


始点Kから1からVまでの数字の場合に必要な最小重み付けと(最短経路)の求め方の問題です.
最初はBFSで解いてみました.

でも…。



タイムアウトではなく、メモリタイムアウトです.
def BFS(n): #도착점 n에 대한 BFS함수
    if k == n:
        return 0

    q = list()
    used = [0]*(v+1)

    for i in range(e):
        if arr[i][0] == k :
            q.append(arr[i])

    while q:
        s = q.pop(0)
        used[s[1]] = 0

        if s[1] == n:
            if not used[s[1]]:
                used[s[1]] = used[s[0]]+s[2]
                return used[s[1]]
            else :
                return used[s[1]]
        for i in range(1, v+1):
            if adj[s[1]][i] == 1 and not used[i]:
                for j in range(e):
                    if [s[1],i,j] in arr:
                        q.append([s[1],i,j])
                        break
                used[s[1]] = used[s[0]]+s[2]

    else :
        return 'INF'

v, e = map(int,input().split())
k = int(input())
arr = [list(map(int,input().split())) for _ in range(e)]
# cnt = 1
# newarr = list()

adj = [[0]*(v+1) for _ in range(v+1)]

for i in range(e):
    for j in range(e-1):
        if arr[j][2] > arr[j+1][2]:
            arr[j][2], arr[j+1][2] = arr[j+1][2], arr[j][2]

for i in range(e):
    adj[arr[i][0]][arr[i][1]] = 1


for i in range(1,v+1):
    print(BFS(i))
重み付けを必要とせずに並べ替え,幹線の数や最大頂点の数に応じて記憶経路のadj配列が大量のメモリを消費すると推定できる.
教授によると、頂点数が1000個を超えると、ほとんどが問題の最大メモリを超えるという.
ただし、メモリオーバーが発生しただけで、メモリオーバーでなければタイムアウトが発生するに違いありません.

やはり



adj配列を使用せずにarr配列に確認してインポートした場合、頂点が2万個の場合、2万回のゲートのキューを回転するたびにbfs関数が呼び出されるたびに返されます.
いずれにしても基本的なBFSは難しいようです.
もしそうなら、木を描いて探索したり、最小のお尻を探す方法で探したりしたほうがいいです.
スレッド同期面接問題
白駿13335トラック