ARC090 E : Avoiding Collision(700)
作成日：2018.02.02
最終更新日：2018.02.02
問題概要
$N$頂点$M$辺からなる連結であるグラフがあり、$i$番目の辺は$U_i$と$V_i$を結び、そこを通過するのに$D_i$だけかかる。
2人の人がそれぞれ頂点$S$,$T$を同時に出発し、$T$,$S$へ最短の時間で移動する。
最短路の選び方の組で、2人が途中で出会うことのないものの個数を$10^9 + 7$で割った余りを求めよ。
制約
$1 \leq N \leq 10^5$
$1 \leq M \leq 2 \times 10^5$
$1 \leq S,T,U_i,V_i \leq N$
$S \neq T , U_i \neq V_i$
$i \neq j$ならば$\{U_i , V_i\} \neq \{U_j , V_j\}$
$1 \leq D_i \leq 10^9$
$D_i$は整数
考え方
2人が出会う時間は、$S$,$T$間の最短路を移動するのにかかる時間の$1/2$(これを$c$とする)である。
出発してから$c$だけ経った時点での場所$p_i$ごとの最短路の数を$w_i$として、$\sum_{i \neq j}{w_iw_j}$を求めれば良い。
求めやすいようにこの式を変形すると$(\sum w_i)^2$$- \sum w_i^2$となる。
これは最短路の数の総数が$\sum w_i$であり、余事象である2人が出会う場合の数が$\sum w_i^2$であることからも導ける。
$w_i$を求めることを考える。
$w_i$は$S$から$p_i$を通って$T$へ行く最短路の数だから、$S$から$p_i$、$p_i$から$T$の最短路の数を掛け合わせたものに等しい。
これは$p_i$が頂点である時は$S$,$T$からその頂点に行く最短路の数、$p_i$が辺上にある時はその辺が結ぶ頂点で$S$,$T$に近いものと$S$,$T$の最短路の数を掛け合わせたものである。
$S$や$T$からある頂点までの最短路の数は、最短路の復元をしながらDPを行えば求められる。
すなわち$S$($T$)からかかる時間を$d_i$とすると、$d_i$が小さい頂点$i$から順に見ていき、$i$と$v$を結ぶ辺$e$で$d_{i}$$+ D_e$$= d_{v}$を満たすものがあったら$v$までの最短路の数に$i$までのものを加えれば良い。
最短路はDijkstraを用いて$O(E \: log \: V)$、$w_i$はすべて合わせて$O(E)$で求めることができるから十分高速である。
ソースコード
マクロ等はこちら
const int MC = 100010;
const LL mod = 1e9 + 7;
const LL INF = 20123456789012345;
int N,M,S,T;
LL z[MC];
vector<P2> V[MC];
priority_queue<P2 , vector<P2> , greater<P2> > Q;
LL ans_s[MC] , ans_t[MC];
int r[MC];
int main(){
cin >> N >> M;
cin >> S >> T;
repp(i,0,M){
int x,y;
LL d;
cin >> x >> y >> d;
d *= 2;
V[x].PB(MP(d,y));
V[y].PB(MP(d,x));
}
fill(z,z+MC,INF);
z[S] = 0;
Q.push(MP(0,S));
while(!Q.empty()){
int x = Q.top().second; Q.pop();
for(auto u : V[x]){
if(z[u.second] > z[x] + u.first){
z[u.second] = z[x] + u.first;
Q.push(MP(z[u.second],u.second));
}
}
}
LL c = z[T] / 2;
ans_s[S] = 1;
ans_t[T] = 1;
repp(i,0,N) r[i] = i+1;
sort(r,r+N,[&](const int &x , const int &y){return z[x] < z[y];});
repp(i,0,N){
for(auto u : V[r[i]]){
if(z[u.second] == z[r[i]] + u.first){
(ans_s[u.second] += ans_s[r[i]]) %= mod;
}
}
}
repm(i,N-1,-1){
for(auto u : V[r[i]]){
if(z[u.second] + u.first == z[r[i]]){
(ans_t[u.second] += ans_t[r[i]]) %= mod;
}
}
}
LL ans0 = 0 , ans1 = 0;
repp(i,1,N+1){
if(z[i] == c){
LL w = ans_s[i] * ans_t[i] % mod;
(ans0 += w) %= mod;
(ans1 += w * w) %= mod;
} else if(z[i] < c){
for(auto u : V[i]) if(z[u.second] == z[i] + u.first && z[u.second] > c){
LL w = ans_s[i] * ans_t[u.second] % mod;
(ans0 += w) %= mod;
(ans1 += w * w) %= mod;
}
}
}
cout << (ans0 * ans0 % mod - ans1 + mod) % mod << endl;
return 0;
}解法まとめ
$S$からの最短路をDijkstraで求める。(22-33行)
経路の復元をしながらDPで$S$($T$)から各頂点までの最短路の数を求める。(35-52行)
$S$から$T$まで行くのにかかる時間の半分$c$の時点での位置$p_i$それぞれについて、$S$から$p_i$を通って$T$へ行く最短路の数$w_i$を求める。
答えは$(\sum w_i)^2$$- \sum w_i^2$である。(53-67行)