[プログラマー]タクシー料金の併用

質問する

精度と効率のテスト

点の個数nは、出発点のsを示し、Aの到着点のaを示し、Bの到着点のbを示し、各点間でタクシー料金を推定するfaresをパラメータとして示す.この場合、A、Bの2人がsから出発し、それぞれタクシーで各到着点まで行くと仮定し、solution関数を1つ完成し、最低1台のタクシーの料金を計算して戻ってください.
思い切ってマイカーで移動しなければ、タクシー料金が安いと予想される場合は、マイカーで移動する必要はありません.

せいげんじょうけん

支点個数nは、3以上200以下の自然数である.

点s,a,bはnより大きい自然数であり,それらの値はそれぞれ異なる.

faresは2次元整数配列である.

fared配列の各行は[c,d,f]フォーマットである.

c時とd時の間の予想タクシー料金はf元です.

入力は、

起点sから到達点aおよびbへの経路が存在する場合にのみ与えられる.

に答える

これは、問題で指定された画像に示すように、グラフィックの問題です.
まず、floodアルゴリズムとshallアルゴリズムを使用して、すべてのノード間の最小距離を検索します.

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if board[i][k] + board[k][j] < board[i][j]:
                    board[i][j] = board[i][k] + board[k][j]

1からnまでのエスケープポイントに必要な金額の最小値を決定するだけです.

    answer = board[s][a] + board[s][b]
    for e in range(n):
        answer = min(answer, board[s][e]+board[e][a]+board[e][b])

この場合、乗り換え(乗り換えなし)がなければ、直接a、bへのタクシー料金が初期値になります.

コード#コード#

def solution(n, s, a, b, fares):
    INF = int(1e9)
    board = [[INF] * n for _ in range(n)]
    
    for c,d,f in fares:
        board[c-1][d-1] = board[d-1][c-1] = f
    for i in range(n):
        board[i][i] = 0
        
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if board[i][k] + board[k][j] < board[i][j]:
                    board[i][j] = board[i][k] + board[k][j]
    
    s,a,b = s-1,a-1,b-1
    answer = board[s][a] + board[s][b]
    for e in range(n):
        answer = min(answer, board[s][e]+board[e][a]+board[e][b])
    return answer