競技プログラミング用 知識集積所
ABC416E - Development
最終更新：
Bot(ページ名リンク)
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
とりあえず、全頂点間の最短距離は常に管理する必要があるので、最短距離を入れる行列（演算しないので実質ただの二次元vector（未作成））は必要。
しかし、Warshall Floyd法（未作成）か、全頂点からDijkstra法（未作成）か、いずれにしてもクエリ3が来るごとに改めて求めていてはとても間に合わない。
そこで、クエリ1や2が来たときに、影響がある部分だけ更新していく方針を取る。
しかし、Warshall Floyd法（未作成）か、全頂点からDijkstra法（未作成）か、いずれにしてもクエリ3が来るごとに改めて求めていてはとても間に合わない。
そこで、クエリ1や2が来たときに、影響がある部分だけ更新していく方針を取る。
クエリ1で、町xと町yの間に新たに道ができた場合。
町iから町jに行く最短経路は
町iから町jに行く最短経路は
- i→j（新しい道を通らない）
- i→x→y→j（i→xとy→jは既存最短経路、x→yは新しい道）
- i→y→x→j（i→yとx→jは既存最短経路、y→xは新しい道）
のいずれかしかありえない。
よって、O(N^2)使ってよければ、新しい道の処理を終えることができる。
よって、O(N^2)使ってよければ、新しい道の処理を終えることができる。
クエリ2で、町に空港ができる場合。
これは実は空を1つの町として、そこへ行くのはコスト0、そこからどこかへ行くのはコストTと考えればよい。
すると、クエリ1と同じ処理でできる。
これは実は空を1つの町として、そこへ行くのはコスト0、そこからどこかへ行くのはコストTと考えればよい。
すると、クエリ1と同じ処理でできる。
クエリ3は、クエリ1や2で合計を常に更新しておけば、ただ出力するだけ。
嫌なクエリばかり来ても、O(Q*N^2)が2.5億なので、どうにか間に合う。
あとは、最初にデータをどう作るかだが、これもWarshall Floyd法（未作成）のO(N^3)で間に合う。
解答例
注意点
空への行き来分を足さないように注意
問題は、町から町への最小コストの総和である。
空への行き来分は関係ないので誤って足さないように。
空への行き来分は関係ないので誤って足さないように。
空の非対称性に気を付ける
空との行き来は、かかるコストが異なる。
i→jの最短を更新するときに、ついでにj→iを更新しようとすると失敗する。
Tが偶数であれば空への行き来でT/2ずつにすることもできるが、Tが奇数ではそれもできない。
全ての値を2倍しておいて、最後に半分にするという手もあるにはあるが……？
i→jの最短を更新するときに、ついでにj→iを更新しようとすると失敗する。
Tが偶数であれば空への行き来でT/2ずつにすることもできるが、Tが奇数ではそれもできない。
全ての値を2倍しておいて、最後に半分にするという手もあるにはあるが……？
全頂点からDijkstra法（未作成）はギリギリ間に合わない
Warshall Floyd法（未作成）はO(N^3)で最大で計算1.25億回。
Dijkstra法（未作成）は最悪O(N+MlogM)で、それを全頂点からやると最大で計算8.31億回。
この見積もりではWarshall Floyd法（未作成）の方が約7倍速い。
だが、実際にやるとほとんどのてすとケースでDijkstra法（未作成）の方が速い。
しかしながら、一部だけDijkstra法（未作成）ではとんでもなく時間がかかるケースがあり、2つだけTLEする。
AtCoder式採点ではV^2<ElogEの場合はWarshall Floyd法（未作成）にしておいたほうがいいらしい。
本番誤答例
Dijkstra法（未作成）は最悪O(N+MlogM)で、それを全頂点からやると最大で計算8.31億回。
この見積もりではWarshall Floyd法（未作成）の方が約7倍速い。
だが、実際にやるとほとんどのてすとケースでDijkstra法（未作成）の方が速い。
しかしながら、一部だけDijkstra法（未作成）ではとんでもなく時間がかかるケースがあり、2つだけTLEする。
AtCoder式採点ではV^2<ElogEの場合はWarshall Floyd法（未作成）にしておいたほうがいいらしい。
本番誤答例
別解
意地でもDijkstra法（未作成）で解く
- 全ての値を2倍しておいて、最後に半分にするのを採用
- 対称性を利用することで、クエリ1や2での更新時にチェック数を半分にできる
- Dijkstra法で、最初から使うことがないとわかっているものはpriority_queueに入れない
- 対称性を利用して、あらかじめわかっている値は入れておく
- 現状の値よりも大きい場合と、現状の値と同じかつそれがDijkstra法内で2回目以降の場合には、priority_queueに入れない
- graph<set<pair>>>をgraph<vector<pair>>>に変更
- 辺の削除がないため、setであるメリットがなく、vectorに変えて高速化できる
