辺が10^5ならダイクストラ使える

頂点が10^5の時、一般的には辺は10^10だが、辺が10^5という追加制約があるならダイクストラ法O((E+V)log V)が使える

辺が10^5の制約