プログラマー72413号-タクシー代(★★/O/1):Python

概要

解答時間:15-20分

時間制限:不明(2秒)

メモリ制限:不明な

製品発表:2021 KAKAO BLIND RECRUITMENT

リンク:https://programmers.co.kr/learn/courses/30/lessons/72413

質問する

[この問題は精度と効率テストで1点ずつ占めています]
夜遅く帰宅した時、安全のためタクシーをよく利用していた武智は最近残業が多くなってきたので、タクシー代の節約を考えていた.「無知」は、自分がタクシーを使うとき、同僚の魚皮奇も自分の方向に似たタクシーをよく使うことを発見した.「無知」は「魚の日」と耳の方向が似ていて、現地でタクシーを乗り合わせればタクシー代をどれだけ節約できるか、「魚の日」に乗り合わせようと提案しています.

上記の例の図は、移動可能半径の6地点間のタクシーの移動可能なタクシー路線と予想料金を示している.
図中のAとBの2人は出発点4番から出発して、タクシーで家に帰るつもりです.Aの家は6日に、Bの家は2日に、二人とも帰宅予定の最低タクシー代はいくらですか.
図

の円は点を示し、円の数字は点番号を示す.

にn個のブランチ機構がある場合、1〜nのブランチ機構番号が使用される.

タクシーが

地点間を移動できる経路を幹線と呼び、幹線に表示される数字は2地点間の予想タクシー料金を示す.

幹線は便利な上線として表示されています.

上図の例では、4番から1番まで(4→1)または1番から4番まで(1→4)の場合、移動方向によってタクシー料金が変化しないと予想される.

の最低タクシー料金は次のように計算されます.

4→1→5:A、Bはタクシーに乗ります.タクシー料金は10+24=34元と予想されています.

5→6:A一人タクシー.タクシー代は2元の予定です.

5→3→2:B一人タクシー.タクシー料金は24+22=46元と予想されています.

A、Bがすべて帰宅する予定の最低タクシー料金は34+2+46=82元.

パラメータは、a,b,a,b,a,b,a,a,a,a,a,a,a,a,a,a,a,a,a,b,a,a,a,a,a,a,b,a,a,a,a,a,a,a,a,b,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,aこのとき、A、Bの2人がsから出発して、それぞれの到着点までタクシーで行くと仮定し、1つの解関数を完成して、最低の推定運賃を計算して、戻ってください.
もし、いっそ便乗せずに各自で移動した場合、タクシー料金がさらに安くなる見込みであれば、便乗する必要はありません.

せいげんじょうけん

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

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

すなわち出発点、Aの到達点、Bの到達点は重複しない.

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

fares配列のサイズは2 nx(n−1)/2より大きい.

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

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

点c,dはnより大きい自然数であり、値はそれぞれ異なる.

費用fは、1以上100000以下の自然数である.

運賃の手配では、2つの場所の間の予想タクシー料金は1つしかありません.すなわち,[c,d,f]があれば,[d,c,f]は与えられない.

入力は、

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

解決策

問題を理解する

あ….この問題は実際の試験では答えられなかった.その時は4問のうち3番でしたか?そうですか.でも今はたぶん感じてる私が成長したからなのか、それとも実際の試験で緊張したからなのか.

アルゴリズム#アルゴリズム#

私の考え方はこうです.

S地点では、複数の出口を通じてすべての番号の最短経路を探します.このとき、AとBの最短距離も保存される.

S地点を除く全ての地点で,その地点からAとBの最短距離を求める.しかし、Sとその点との距離がAとBとの最短距離を超えると、まったく要求が不要となるため、不要な演算は行われない.

このように更新AとBの最短距離は

を終了する.

Python

マイコード

import heapq
INF = int(1e9)

def dijkstra(n, graph, s):
    distance = [INF] * (n + 1)
    distance[s] = 0
    
    q = []
    heapq.heappush(q, (0, s))
    while q:
        dist, now = heapq.heappop(q)
        
        if distance[now] < dist:
            continue
        
        for i in graph[now]:
            cost = distance[now] + i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    
    return distance


def solution(n, s, a, b, fares):
    graph = [[] for _ in range(n + 1)]
    
    for fare in fares:
        c, d, cost = fare
        graph[c].append((d, cost))
        graph[d].append((c, cost))
    
    # s부터해서 최소 이동 경로를 구함
    distance = dijkstra(n, graph, s)
    result = distance[a] + distance[b]
    
    # 1 ~ n 지점
    for i in range(1, n + 1):
        # ✅ i가 s이거나 s에서 해당 지점과의 거리가 result와 같거나 더 큰경우는 구할 필요 없음
        if result <= distance[i] or i == s: 
            continue
        else:
            # 나머지는 다익스트라를 계산해서 result 업데이트
            dist = dijkstra(n, graph, i)
            result = min(result, distance[i] + (dist[a] + dist[b])) # s에서 i로 이동 + i에서 a와 b로 이동
    
    return result

効率が落ちるのではないかと心配したが、幸い成功した.久しぶりにこの謎を解いたので、コードを見なくてもいいです.30分以内に成功しました(やれやれ~)

コメントコード

import heapq

def solution(n, s, a, b, fares):
    d = [ [ 20000001 for _ in range(n) ] for _ in range(n) ]
    for x in range(n):
        d[x][x] = 0
    for x, y, c in fares:
        d[x-1][y-1] = c
        d[y-1][x-1] = c

    for i in range(n):
        for j in range(n):
            for k in range(n):
                if d[j][k] > d[j][i] + d[i][k]:
                    d[j][k] = d[j][i] + d[i][k]

    minv = 40000002
    for i in range(n):
        minv = min(minv, d[s-1][i]+d[i][a-1]+d[i][b-1])
    return minv

# 소스 코드 참고 : https://programmers.co.kr/learn/courses/30/lessons/72413/solution_groups?language=python3

他の人のコードを見ると、nはせいぜい200以下なので、floywalshで解くこともできます.ただ、私のコードに比べて効率が低いです.1秒以上記録されているのがわかります