[プログラマー]タクシー料金の併用
質問する
精度と効率のテスト
点の個数nは、出発点のsを示し、
Aの到着点のaを示し、Bの到着点のbを示し、各点間でタクシー料金を推定するfaresをパラメータとして示す.この場合、A、Bの2人がsから出発し、それぞれタクシーで各到着点まで行くと仮定し、solution関数を1つ完成し、最低1台のタクシーの料金を計算して戻ってください.思い切ってマイカーで移動しなければ、タクシー料金が安いと予想される場合は、マイカーで移動する必要はありません.
せいげんじょうけん
に答える
これは、問題で指定された画像に示すように、グラフィックの問題です.
まず、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] answer = board[s][a] + board[s][b]
for e in range(n):
answer = min(answer, board[s][e]+board[e][a]+board[e][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 answerReference
この問題について([プログラマー]タクシー料金の併用), 我々は、より多くの情報をここで見つけました https://velog.io/@haman/프로그래머스-합승-택시-요금テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol