まず、$S$から各頂点への最短時間$d_s(v)$は、ダイクストラで求めることができます。このときに、$S$から各頂点に最短時間で行く方法の通り数$c_s(v)$も、ダイクストラに3行ほどコードを書き足すことで求めることが可能です。このときに使うアルゴリズムは、格子状のある交点からある交点に行く道順は何通りあるかを求めるアルゴリズムです。
同様の方法で、$T$から各頂点への最短時間$d_t(v)$と、$T$から各頂点に最短時間で行く方法の通り数$c_t(v)$も求められます。
最終的に求めたいものは「二人が出会うことのないものの個数」です。これは、すべてのものの個数から、二人が出会うものの個数を引けばよいです。すべてのものの個数は$c_s(T)^2$（または$c_t(S)^2$）で求められます。二人が出会うものの個数ですが、頂点で出会うときと辺で出会うときとで場合分けして考えます。
$S$から$T$への最短時間を$X$とおくと、$d_s(v) = X/2$かつ$d_t(v) = X/2$であるような頂点$v$が、二人が出会う可能性のある頂点です。経路の個数は$(c_s(v) \times c_t(v))^2$です。この式は、高橋くんと青木くんの経路の選び方は完全に独立していること、$S$から$T$まで$v$を通って行く経路の個数は$c_s(v) \times c_t(v)$であることから導き出されます。
ある辺$e$で出会うとき、$e$の端点を$v, u$とおくと、$(d_s(v) < X/2) \land (d_s(u) > X/2)$が成り立ちます。