問題

解法

（計算量に関しては自信ないです）

$(U,\ S)$ を頂点とみなす。ただし、 $U$ は都市、 $S$ は持っている銀貨の枚数を表す
銀貨の枚数は $S_{max} = A_{max} \cdot (N - 1)$ より多く持っていても意味がないので、頂点数は $O(N \cdot S_{max})$ で済む。

上記のように頂点を増やした場合、辺は鉄道路線と両替の2種類存在する。
鉄道路線を使う場合、頂点 $(U,\ S)$ から頂点 $(V,\ S - A)$ に $B$ 分かけて移動する。ただし、銀貨が $A$ 枚以上必要である。
両替をする場合、 $(U,\ S)$ から $(U,\ max(S_{max},\ S + C))$ に $D$ 分かけて移動する。
鉄道路線の辺数は $O(M \cdot S_{max})$ 、両替の辺数は $O(N \cdot S_{max})$ なので、合計の辺数は $(M + N) \cdot S_{max}$ となる。