初めに、各町から出発したときの最短距離を求めます。
これは始点を $K$ 個のショッピングモールとする多始点ダイクストラ法で $O(N \log M)$ で求めることができます。

次に、町 $a$ と町 $b$ を結ぶ長さ $l$ の道路 $R$ 上にある点から出発した際、最短距離が最長となるようなものを求めます。 $a$ からの最短距離を $X$ とし、 $b$ からの最短距離を $Y$ とします。また、 $X \leq Y$ とします。
このとき、 $X+l \geq Y$ です。なぜなら、 $X+l < Y$ ならば町 $b$ から町 $a$ へ $R$ をたどっていき、その後 $a$ から最短経路を通ことで町 $b$ から距離 $X+l$ でショッピングモールに行くことができるので、矛盾するためです。

$a$ から $f$ 離れた $R$ 上の点 $P$ について、点 $P$ からの距離は $\min(X+f,Y+l-f)$ です。 $X+f$ と $Y+l-f$ の和は $X+Y+l$ で一定であるため、 $X+f=Y+l-f$ となる$f$ が最適となり、このような $f$ は $\frac{Y-X+l}{2}$ となります。 $X+l \geq Y$ より $Y-X \leq l$ なので $f = \frac{Y-X+l}{2} \leq l$ となり最適となる点 $P$ は必ず $R$ 上に存在します。

以上の考察より、辺上にある点からの場合は \(O(M)\) で考えられるので \(O(N \log M +M)\) でこの問題を解くことができました。