[レベル3/グラフ]タクシー料金+SWIFT

質問リンク

コードテスト練習-タクシー料金の併用

Floyd Warshallアルゴリズム

ノード1からノード5の場合は、次のようになります.

1→2→3→5:費用は1+3+1で、合計5です.

1→2→5:費用1+2、合計3.

1→4→5:費用2+2、合計4.

したがって、1から5までの最小料金は3です.フロイドアルゴリズムはこの場合に有用である.

質問する

パラメータは、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つの解関数を完成して、最低の推定運賃を計算して、戻ってください.もし、いっそ便乗せずに各自で移動した場合、タクシー料金がさらに安くなる見込みであれば、便乗する必要はありません.

入力

let n = 6
let s = 4
let a = 6
let b = 2
let fares = [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]]

しゅつりょく

82

問題を解く

ノードからノードへの費用を格納するdb 2層配列を作成します.費用のデフォルトは、最大費用(100000)を超える99999999です.

料金表を1つずつ追加する費用.例えば、第1の再要素[4,10]については、ノード4~1の費用が10であるため、db[1][4]およびdb[4][1]に費用10が格納される.

これはフロイドとシエルアルゴリズムの核心です.ドアに3回使用し,iからkまでの最小費用を格納する.
例えば、i=4、j=1、k=6とする.上図に示すように、4～6の料金は50です.4から1までの費用10と1から6までの費用25を合わせた費用は35より大きい.dbは4~6の料金db[4][6]を2つの合計の料金(db[4][1]+db[1][6])に更新する.

sから中間点kまでの費用とkからaとkからbまでの費用の和を求めて、最高価格を探します.中間点のkがs値と一致すると,乗算ではなくそれぞれの移動と見なすことができる.

import Foundation

func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
    var db: [[Int]] = Array(repeating: Array(repeating: 999999, count: n+1), count: n+1)
    var minFare = 9999999
    
    for fare in fares {
        db[fare[0]][fare[1]] = fare[2]
        db[fare[1]][fare[0]] = fare[2]
    }
    
    for k in 1...n {
        for i in 1...n {
            for j in 1...n {
                if i == j { db[i][j] = 0 }
                if db[i][j] > db[i][k] + db[k][j] {
                    db[i][j] = db[i][k] + db[k][j]
                }
            }
        }
    }
    
    for midpoint in 1...n {
        let fare = db[s][midpoint] + db[midpoint][a] + db[midpoint][b]
        if minFare > fare { minFare = fare }
    }
    
    return minFare
}

let answer = solution(n, s, a, b, fares)
print(answer)