E -Avoiding Collision

E - Avoiding Collision

二人が最短で動く方法から出会う組み合わせを引く

sからtへの最短距離をdとする
すると二人が出会うのはd/2移動したとき

ところで、ある頂点iにいる時の時刻は一定なので
diss[v] := sからvへ移動するのにかかる時間
dist[v] := tからvへ移動するのにかかる時間とできる

二人が頂点上で出会う場合
頂点vとしてあり得るものは　 diss[v] == dist[v] == d / 2 となるもの

二人が辺上で出会う場合
両端点v,uとしてあり得るものは　diss[v] < d / 2 && diss[v] + 辺コスト > d / 2 && diss[v] +辺コスト + dist[u] == d (つまりvuを通って最短となる)を満たすもの

それぞれの頂点について最短で行ける組み合わせ数を数えておけば、かけ合わせで答えがわかる

Submission #4264034 - AtCoder Regular Contest 090

int s, t;
undigraph<> g(2 * k5);
vi ds, dt;
void dfs(int i, vi &dis, vm &cou) {
    priority_queue<P, vector<P>, greater<P> > q;//小さい順
    q+=mp(-0,i);
    vb us(k5);
    while (q.size()){
        int nc = q.top().F;
        int v = q.top().S;
        q.pop();
        forg(gi, g[v]){
            if(nc+c==dis[t]){
                cou[t] += cou[f];
                if(!us[t])q.emplace(dis[t],t);
                us[t]=1;
            }
        }
    }
}

void solve() {
    setMod();
    cin >> n >> m >> s >> t;
    --s, --t;
    rep(i, m) {
        int f, s, c;
        cin >> f >> s >> c;
        --f, --s;
        g.add(f, s, c);
    }
    ds = dijkstra(g, s);
    dt = dijkstra(g, t);
    int d = ds[t];
    vm coul(k5), cour(k5);
    coul[s] = 1;
    cour[t] = 1;
    dfs(s, ds, coul);
    dfs(t, dt, cour);
    mint res = coul[t]  * cour[s];
    rep(i, n) {
        int nc = ds[i];
        if (nc * 2 == d)res -= coul[i] * cour[i]*coul[i] * cour[i];
        forg(gi, g[i]) {
            int tc = nc + c;
            //必要最短経路に含まれていたら
            int allc = tc + dt[ t];
            if (nc * 2 < d && tc * 2 > d && allc == d) {
                res -= coul[i]*coul[i] * cour[t]* cour[t];
            }
        }
    }
    cout << res << endl;
}