Zenn
Open10

最短経路問題

Julia
AtCoder
mk83mk83

GW中に最短経路問題くらいはクリアできるようになりたいという強い気持ちで

https://atcoder.jp/contests/abc051/tasks/abc051_d

をやっています。
以下のコードだと、サンプルと本番の８問は通るけど、あとはTLEとWAとREになります。
TLEは毎回グラフ作り直しているから。WAはグラフの作り方がおかしいから。
REはわからないけど、反復回数とかでしょうか。

解説のメイン解法ではなく、各頂点からダイクストラ法を全部回すという方針で始めました。

pythonistaの方のコードを見たので、明日はそれをjuliaで再現してみようと思います。とにかくグラフ構築は１度にするべき。

通らなくても動くコードをかく、という最低目標はクリアしました。（自己愛ムーブ）

function add_edge!はmutable structでグラフを作ろうとした名残。

mk83mk83

コード１

int(x) = parse(Int, x)
readint() = readline() |> int
readints() = readline() |> split .|> int

function add_edge!(g, tail, head, cost)
    g[tail, head] = cost
    g[head, tail] = cost
end

function shortest_path(s, t, n, g, adj)
#     println("start ", s, " end ", t)
    previous = [-1 for _ in 1:n]
    visited = [false for _ in 1:n]
    cost = [10^9 for _ in 1:n]

    current = s
    cost[s] = 0
    visited[s] = true

    while current != t
        best = 10^9
        next = -1
        for p in adj[current]
            visited[p] && continue
                cost[p] = cost[current] + g[current, p]
                previous[p] = current
            end
            if cost[p] < best
                best = cost[p]
                next = p
            end
        end
        if next == -1
            current = previous[current]
            continue
        end
        visited[next] = true
        current = next
    end

    return (cost[t], previous)
end

function main()
    n, m = readints()
    g = zeros(Int, n,n)
    adj = [[] for _ in 1:n]
    edge_set = Set{Tuple}()
    for i in 1:m
        a,b,c = readints()
        add_edge!(g, a, b, c)
        push!(adj[a], b)
        push!(adj[b], a)
        push!(edge_set, (a, b))
    end
    used_edge = Set()

    for s in 1:n
        for t in s:n
            s == t && continue
            cost, previous = shortest_path(s,t,n,g,adj)
            current = t
            while current != s
                next = previous[current]
                if next < current
                    push!(used_edge, (next, current))
                else
                    push!(used_edge, (current, next))
                end
                current = next
            end
        end
    end
    println(length(setdiff(edge_set, used_edge)))
end

main()
mk83mk83

明日のための忘備

  • max(cost[i], cost[j] + cost[j, i])で書ける
mk83mk83

昨日考察したことであっているのは「グラフを１回だけつくる」というところだけ。

解法としては、

  1. ワーシャルフロイド法で、全ノード間の最短距離を求めます。
  2. すべてのエッジについて、元のエッジの長さと最短距離が異なるかどうかをチェックし、異なれば最短経路に含まれていないとしてカウントします。
mk83mk83
int(x) = parse(Int, x)
readint() = readline() |> int
readints() = readline() |> split .|> int


function add_edge!(g, tail, head, cost)
    g[tail, head] = cost
    g[head, tail] = cost
end

function warshall_floyd(cost, n)
    for k in 1:n
        for i in 1:n
            for j in 1:n
                cost[i, j] = min(cost[i, j], cost[i, k] + cost[k, j])
            end
        end
    end
end

function main()
    n, m = readints()
    g = fill(10^5, n, n)
    for i in 1:n
        g[i, i] = 0
    end
    edges = []

    for i in 1:m
        a,b,c = readints()
        add_edge!(g, a, b, c)
        push!(edges, (a, b, c))
    end

    prev = warshall_floyd(g,n)

    counter = 0
    for k in 1:m
        a, b, c = edges[k]
        if g[a, b] != c
            counter += 1
        end
    end
    println(counter)
end

main()
mk83mk83

経路復元しようとした跡が残っていますね…

mk83mk83

ワーシャルフロイド法は理解しやすいと思いましたが、経路復元がうまくできるかイメージできませんでした。保留案件。

mk83mk83

Juliaでpriority queueが実装できなかったので、pythonでやった。ただ、満点を取りに行ったとき、TLEとMLEが発生した。

from typing import List
from heapq import heapify, heappop, heappush


def isempty(l: List):
    return len(l) == 0


def djikstra(s, graph, adj, n):
    path = [0 for _ in range(n + 1)]
    dist = [float("Inf") for _ in range(n + 1)]
    dist[s] = 0

    candidates = [(0, s)]
    heapify(candidates)

    while isempty(candidates) is False:
        current_cost, current_pos = heappop(candidates)
        if current_cost > dist[current_pos]:
            continue
        for successor, next_cost in adj[current_pos]:
            tmp_cost = dist[current_pos] + graph[current_pos][successor]
            if dist[successor] <= tmp_cost:
                continue
            dist[successor] = tmp_cost
            path[successor] = current_pos
            heappush(candidates, (tmp_cost, successor))
    return dist


def main():
    n, m, t = list(map(int, input().split()))
    A = list(map(int, input().split()))
    g = [[0] * (n + 1) for _ in range(n + 1)]
    g_rev = [[0] * (n + 1) for _ in range(n + 1)]
    adj = [[] for _ in range(n + 1)]
    adj_rev = [[] for _ in range(n + 1)]

    for i in range(m):
        a, b, c = list(map(int, input().split()))
        g[a][b] = c
        g_rev[b][a] = c
        adj[a] += [(b, c)]
        adj_rev[b] += [(a, c)]

    revenue = [0 for _ in range(n + 1)]
    best = t * A[0]

    forward = djikstra(1, g, adj, n)
    backward = djikstra(1, g_rev, adj_rev, n)

    for visit in range(2, n + 1):
        revenue[visit] = (t - forward[visit] - backward[visit]) * A[visit - 1]
        if best < revenue[visit]:
            best = revenue[visit]

    print(best)
    return


if __name__ == "__main__":
    main()
mk83mk83

ダイクストラ法ってもっと簡単に実装できていた気がするんですが…（同僚たちのコードを思い返すと）。
とりあえず、TLE脱出なんかも考えつつ、ベルマン＝フォード法もやってみたい。