Count Number of Shortest Path w/ Floyd-Warshall

Floyd-Warshall로 최단 경로의 개수를 셀 수가 있는데. 3중 포문을 돌면서 거리와 count를 같이 갖고 있으면서 돌리면 된다.

예를 들어 현재 Dist(j, k) > Dist(j, i) + Dist(i, k) 라서 업데이트 된다면,

Count(j, k) = Count(j, i) *  Count(i, k) 이고,

Dist(j, k) == Dist(j, i) + Dist(i, k) 라면

Count(j, k) += Count(j, i) *  Count(i, k) 이다.

초기 조건은 주어지는 에지들이면 Count 1 아니면 0 이런 식이면 된다.

신기함 ㅋㅋ

연습 문제 : http://wcipeg.com/problem/noi07p1