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]

これらを引いてやればいいですね

初心忘れるべからず..