[最短距離]タクシー料金の併用

1450 ワード
テキストリンク
質問する
これはflowersalアルゴリズムを適用すれば解決できる問題である.
flowersalアルゴリズムはO(n^3)複雑度を有し,ノード数はあまり多くできない.しかし,問題ではノード数が200個以下であるため可能である.
主なアイデアは次のとおりです.
FlowedWarcialを使用して最小原価表を作成し、各ノードの原価の合計(原価表のa、b、および開始原価の合計)を計算します.
共乗しない場合を考慮して、sにおいてa,bがそれぞれ最小費用和より小さい場合に共乗する.
def solution(n, s1, a1, b1, fares):
    INF = int(1e9)
    graph = [[INF for _ in range(n+1)] for _ in range(n+1)]

    for a in range(1, n+1):
        for b in range(1, n+1):
            if a==b:
                graph[a][b] = 0

    for f in fares:
        a, b, c = f
        # 양방향 모두 비용 추가
        graph[a][b] = c 
        graph[b][a] = c
        
	# 플루이드-워셜 알고리즘
    for k in range(1, n+1):
        for a in range(1, n+1):
            for b in range(1, n + 1):
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
	
    # 최소비용 계산
    small = INF
    for i in range(1, n+1):
        if small > (graph[i][a1] + graph[i][b1] + graph[i][s1]):
            small = graph[i][a1] + graph[i][b1] + graph[i][s1]
     
     # 합승안하는 경우까지 생각     
    if small > graph[s1][a1] + graph[s1][b1]:
        return graph[s1][a1] + graph[s1][b1]
     
    return small
に感銘を与える
初めて問題を見たときは難しそうでしたが、Daestra、FlowedWaterの原理を学ぶときは、学習の開始ノードや到達ノードを基準に考えるのではなく、거쳐가는 중간 노드を基準に考えるので、アイデアが出ました.
怖がらないで!
もっと辛い
スタック、キューアルゴリズム