愚直にダイクストラ法で解こうとすると頂点数が$ \mathcal{O}(N)、辺が$ \mathcal{O}(N^3)になってTLEする 以下の最良優先探索を枝刈りしながら行うとC++では間に合う 4種類の内、上3種類は訪問先のコストが今計算した結果より大きいなら移動してキューに入れる 一番下の移動は現在の点に近い方から見ていく その点が既に…