#AtCoder #ABC #ABC070 #D #400pt https://atcoder.jp/contests/abc070/tasks/abc070_d すべてのクエリで頂点Xと頂点Kの距離+頂点Yと頂点Kの距離を出せば良い Kが共通なので先にKを始点としてダイクストラ法で最短距離を求めれば、各クエリは$ O(1)になるので全体で$ O(N \log N + Q) ($ V+E = N