GoBigorGoHome/main.txt

## main.txt
両替を都市 i で行う場合、kenkoooo さんが払う金額は「s から i に円による支払いで移動する際の最小金額」円と「i から t にスヌークによる支払いで移動する際の最小金額」スヌークになります。これらの和を最小化するような都市 i を求めればよいです。「 i から t にスヌークによる支払いで移動する際の最小コスト」と「 t から i にスヌークによる支払いで移動する際の最小コスト」は同じであるため、「 s から i に円による支払いで移動する際の最小金額」と「 t から i にスヌークによる支払いで移動する際の最小金額」が求まれば良いです。「s から i に円による支払いで移動する際の最小金額」を求めるために、問題を n 頂点 m 辺の重み付きグラフの問題とみなします。このとき「s から i に円による支払いで移動する際の最小金額」は「s から i への最短経路帳」になります。s から各 i への最短経路長はダイクストラ法を用いると、O((n + m) log n) 程度で求めることができます。「t から i にスヌークによる支払いで移動する際の最小金額」も同様の方法で求めることができます。

When exchanging money in city i, the amount paid by kenkoooo is "the minimum amount when moving from payment by yen to s from i" yen and "the minimum amount when moving by payment by snook to i from t to snook" Become. You can find a city i that minimizes these sums. "Minimum cost when moving with payment by snook to i from t" and "Minimum cost when moving with payment by snook to t from i" are the same, so "move from s to i by payment by yen Minimum amount of money "and" Minimum price when moving by payment by Snook to t from i "should be obtained. In order to find "the minimum amount when moving by payment by yen from s to i", we regard the problem as a problem of weighted graph of n vertex m side. At this time "Minimum amount when you move by payment with yen from s to i" is "shortest path book from s to i". The shortest path length from s to each i can be obtained by O ((n + m) log n) when Dijkstra's method is used. "Minimum amount when you move with payment by Snook to t from i" can be obtained in the same way.
	両替を都市 i で行う場合、kenkoooo さんが払う金額は「s から i に円による支払いで移動する際の最小金額」円と「i から t にスヌークによる支払いで移動する際の最小金額」スヌークになります。これらの和を最小化するような都市 i を求めればよいです。「 i から t にスヌークによる支払いで移動する際の最小コスト」と「 t から i にスヌークによる支払いで移動する際の最小コスト」は同じであるため、「 s から i に円による支払いで移動する際の最小金額」と「 t から i にスヌークによる支払いで移動する際の最小金額」が求まれば良いです。「s から i に円による支払いで移動する際の最小金額」を求めるために、問題を n 頂点 m 辺の重み付きグラフの問題とみなします。このとき「s から i に円による支払いで移動する際の最小金額」は「s から i への最短経路帳」になります。s から各 i への最短経路長はダイクストラ法を用いると、O((n + m) log n) 程度で求めることができます。「t から i にスヌークによる支払いで移動する際の最小金額」も同様の方法で求めることができます。

	When exchanging money in city i, the amount paid by kenkoooo is "the minimum amount when moving from payment by yen to s from i" yen and "the minimum amount when moving by payment by snook to i from t to snook" Become. You can find a city i that minimizes these sums. "Minimum cost when moving with payment by snook to i from t" and "Minimum cost when moving with payment by snook to t from i" are the same, so "move from s to i by payment by yen Minimum amount of money "and" Minimum price when moving by payment by Snook to t from i "should be obtained. In order to find "the minimum amount when moving by payment by yen from s to i", we regard the problem as a problem of weighted graph of n vertex m side. At this time "Minimum amount when you move by payment with yen from s to i" is "shortest path book from s to i". The shortest path length from s to each i can be obtained by O ((n + m) log n) when Dijkstra's method is used. "Minimum amount when you move with payment by Snook to t from i" can be obtained in the same way.