ARC090-E Avoiding Collision
何するか分かるけど、どうしたらいいのか分からないことが多かったので 書いておく
解法
1.S から各頂点への距離をDijkstraで求める
2.S から各頂点への経路数
各頂点からTへの経路数を求める
3.(全経路の組み合わせ) - (すれ違ってしまう組み合わせ) が答え
計算方法が分からず
1.は分かる
最短経路は必ずDAGになる(これは分かる)
dpをすれば経路数が分かるのだが
簡単に計算する方法があり
vector<P> vec; for(int i = 1;i <= n;i++) vec.push_back({dist[i] , i}); sort(vec.begin(),vec.end());
とすることで、Sから近い順に頂点を取り出すことができるので
この頂点順に沿って
for(int i = 0;i < n;i++) { for(auto & e : edges[vec[i].second]) { if(dist[e.to] == dist[vec[i].second] + e.cost) (dp_t[e.to] += dp_t[vec[i].second]) %= MOD; } }
としてやれば経路数が分かる
また各頂点からTまでの経路数は逆からやっていけばいい
for(int i = n - 1;i >= 0;i--) { for(auto & e : edges[vec[i].second]) { if(dist[vec[i].second] == dist[e.to] + e.cost) (dp_s[e.to] += dp_s[vec[i].second]) %= MOD; } }
全経路の組み合わせは
dp_t[t] * dp_s[s]
すれ違う可能性のあるのは
頂点か辺
頂点...
出会うタイミングのあるのは
dist[v] * 2 = dist[t];
となっている頂点v
経路の組み合わせの数は S -> v -> T と T -> v -> S の組み合わせなので
dp_t[v] * dp_s[v] * dp_s[v] * dp_t[v]
辺...
出会うタイミングは
辺の両端の頂点をu,vとすると
2 * dist[u] < dist[t] && dist[t] < 2 * dist[v]
&& dist[u] + cost == dist[v]
を満たす辺である
経路の君合わせの数は S -> u -> v -> T と T -> v -> u -> S の組み合わせなので
dp_t[u] * dp_s[v] * dp_s[v] * dp_t[u]
これらを引いてやればいいですね
初心忘れるべからず..