Problem 3 - nisshiee/takashi GitHub Wiki

ダイクストラ法で解いた。

工夫

最小運賃経路と最小距離経路の分岐を、いかにコード重複なく実現するか。 自分の知識内のScala黒魔術を最大限使う。

まず、「距離を取得できる型クラス」と「運賃を取得できる型クラス」を作り(https://github.com/nisshiee/takashi/blob/master/src/main/scala/prob3/Cost.scala#L41-49)、 Edge case classに対してこの両方のインスタンスを実装(https://github.com/nisshiee/takashi/blob/master/src/main/scala/prob3/Graph.scala#L9-14)。

次に「コストを取得できる型クラス」を同様に作り、 この型クラスのインスタンスは、「Tags.Distance」「Tags.Fee」というタグに対するTagged Typeに対して実装する。 (https://github.com/nisshiee/takashi/blob/master/src/main/scala/prob3/Cost.scala#L12-22)

あとは、必要なimplicit value, conversionをスコープに入れておけば、 型パラメータの指定だけで運賃と経路、どちらを「コスト」として取り出すかを分岐できる。 (https://github.com/nisshiee/takashi/blob/master/src/main/scala/prob3/Takashi.scala#L10-11)