paizaラーニング リアルイベント問題セット: 最小の運賃(Python 解答例)

スポンサーリンク

追記(2021年05月19日)

Pythonでのダイクストラ法を復習したところ、多少まともなコードが書けるようになったのでコードを更新しておく。詳しい解説は別の記事で。

新しいコード

import heapq


class State:
    def __init__(self, node, cost):
        self.node = node
        self.cost = cost

    def __lt__(self, state):
        return self.cost < state.cost


def dijkstra():
    total_costs = [float('inf') for _ in range(v)]
    open_que = []
    closed_que = set()
    state = State(s, 0)  # node,cost
    heapq.heappush(open_que, state)

    while len(open_que) > 0:
        state = heapq.heappop(open_que)
        if state in closed_que:
            continue
        closed_que.add(state)

        for i in range(v):
            if g[i][state.node] == 'NA':
                continue
            next_cost = state.cost + g[state.node][i]
            if total_costs[i] <= next_cost:
                continue
            total_costs[i] = next_cost
            heapq.heappush(open_que, State(i, next_cost))

    return total_costs[t]


s = 0
e, v, t = map(int, input().split())
g = [["NA"] * v for _ in range(v)]

for _ in range(e):
    tmp1, tmp2, tmp3 = map(int, input().split())
    g[tmp1][tmp2] = tmp3
    g[tmp2][tmp1] = tmp3

answer = dijkstra()
print(answer)

追記ここまで

はじめに

paizaのリアルイベント問題において、「最小の運賃」は正解率が18.0%と一番低い。このコードには色々不満があって修正したいのだが、一応満点が取れたし、検索しても他に誰も解答を公開していないので、誰かの参考になるかもしれないということで公開しておく。

pandasを使っていることもあり動作が遅い。本当はもっとマシなコードの書き方があるはず。あくまで初心者のコードなのでご参考まで。基本的な考え方はダイクストラ問題と同じ。heapqとかclassが上手く使えれば、スッキリとした速いコードが書けると思う。

paizaの問題へのリンク(リアルイベント問題セット

コード全体

import pandas as pd

e, v, t = map(int, input().split())
INF = float('inf')
g = [[INF] * v for _ in range(v)]

for _ in range(e):
    a, b, c = map(int, input().split())
    g[a][b] = c
    g[b][a] = c

next_list = [[0, 0]]  # position,cost
closed_list = []
df_n = pd.DataFrame(next_list, columns=['pos', 'cost'])
df_c = pd.DataFrame(closed_list, columns=['pos', 'cost'])

flag = 0
while flag == 0:
    # breakpoint()
    pos, c = df_n.iloc[0]
    df_n.drop(index=[0], inplace=True)
    for i in range(v):
        c_n = g[pos][i]
        pos_n = i
        if c_n == INF:
            continue
        if ((df_c['pos'] == pos_n) & (df_c['cost'] <= c + c_n)).any():
            continue
        if ((df_n['pos'] == pos_n) & (df_n['cost'] <= c + c_n)).any():
            continue
        df_n = df_n.append({'pos': pos_n, 'cost': c + c_n}, ignore_index=True)

    df_c = df_c.append({'pos': pos, 'cost': c}, ignore_index=True)
    if len(df_n) <= 0:
        flag = 1
    df_n.sort_values('cost', inplace=True)
    df_n.reset_index(inplace=True, drop=True)

target = df_c[df_c['pos'] == t]
ans = min(target['cost'])
print(ans)

「pandasでpaiza問題」記事一覧へのリンク

コメント

当ブログのコンテンツが気に入ったら広告ブロックの解除(ホワイトリスト化)をご検討下さい。

Please disable your adblocker or whitelist this site!

タイトルとURLをコピーしました