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より大きい.
例えば、

、n=6の場合、fares配列のサイズは2または15より大きい.(6 x 5/2 = 15)

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

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

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

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

運賃の手配では、2つの場所の間の予想タクシー料金は1つしかありません.

、すなわち[c,d,f]がある場合、[d,c,f]は提供されない.

入力は、

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

に答える

方法

最短経路を求める問題といえば,2つのアルゴリズムが考えられる.
1.ケーキ
2.フロイドとシエル
どちらのアルゴリズムもDP方式のアルゴリズムである.
最短距離は複数の最短距離からなるためである.
すなわち,最短距離を求める場合には,以前に求めた最短距離情報が保持される.
2つのアルゴリズムの違いは次のとおりです.
複数のカーブの場合、1つのノードから別のノードまでの最短距離を求めることができます.
フロイドとシエルは,すべてのノードから他のノードまでの最短距離を求めることができる.
共乗点がcの場合、
問題から救うのは
s->c:始点から終点までの最短距離
c->a:共乗点からa到達点までの最短距離
c->b:共乗点からb到達点までの最短距離
この3つを合わせると最小値です.
(合乗がなければ、c->aまたはc->bのいずれかを0と見なすことができる)
最終的には、各ノードからすべてのノードまでの最短距離が得られる.
これはフロイドとシエルアルゴリズムを用いた問題である.

フロイドとシエル

https://blog.naver.com/ndb796/221234427842
上のブログには原理が詳しく記載されています.
このアルゴリズムの核心は
通過するノードを基準にアルゴリズムを実行する.
DP原理により,従来の最短距離を継続し,ノードを通過するたびに更新する.
点火式.
a出発、b到着、
cが通過するノードであると仮定すると、
a->b距離(f[a][b])と
a->c->b距離(f[a][c]+f[c][b])を比較し、より小さく更新します.
f[a][b] = min(f[a][b], f[a][c] + f[c][b])

ソースコード

from math import inf

def solution(n, s, a, b, fares):
    answer = 0
    # 그래프 초기화
    graph = [[inf]*n for _ in range(n)]
    for f in fares:
        graph[f[0]-1][f[1]-1] = f[2]
        graph[f[1]-1][f[0]-1] = f[2]
    for i in range(n):
        graph[i][i] = 0

    # 플로이드 와샬
    for k in range(n):  # 거쳐간 노드
        for i in range(n):  # 출발 노드
            for j in range(n):  # 도착 노드
                if graph[i][k]+graph[k][j] <= graph[i][j]:
                    graph[i][j] = graph[i][k]+graph[k][j]

    # 합승지점 별 최소값 리스트
    c_list = [0]*n

    # 합승 지점이 c일때 (s->c) + (c->a) + (c->b) 최소값 구하기
    for c in range(n):
        c_list[c] = graph[s-1][c] + graph[c][a-1] + graph[c][b-1]

    answer = min(c_list)
    return answer

フロイドとシエルとダエストラの概念を思い出すのは難しく、ヒントだけが見えた.
上の概念さえ考えれば、難しくないようです.
やっぱりもっと問題を作るんですね~