https://emtubasa.hateblo.jp/entry/2019/08/14/013000

解法

まずは、陸路と海路それぞれについて、ワーシャルフロイド法を用いて、任意の町間の最短距離を計算しておきます。町 $i$ から町 $j$ の最短経路について、陸路を $l_{ij}$ 、海路を $s_{ij}$ とします。
そして、DPを行います。
$dp[i][j] = i$ 回目の集配を終えた時点で、船が町 $j$ にあるような経路の中で、時間が最短のもの
とします。そして、 $i$ 回目の集配を陸路のみで行うか、海路も含めて行うかの2パターンに分けて計算します。
初期値は、 $dp[1][j] = s_{z_1 \ j}$ となります。

陸路のみを利用する場合
$i$ 回目の集配を終えても、その前後で船の位置は移動しません。ので、
$dp[i][j] = min(dp[i][j] ,dp[i - 1][j] + l_{z_{i -1 } \ z_{i}} )$
となります。
海路も利用する場合
町 $k$ から町 $j$ まで海路を利用したとします。すると、
$(z_{i - 1}からkまでの陸路) + (kからjまでの海路) + (jからz_{i}までの陸路)$
が今回かかる時間なので、
$dp[i][j] = min(dp[i][j] , dp[i - 1][k] + l_{z_{i - 1} \ k} + s_{k \ j} + l_{j \ z_{i}} )$
となります。

あとは、このDPを行い、 $dp[r][j]$ の最小値を求めれば答えとなります。