티스토리 뷰

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

'공부 > Problem solving' 카테고리의 다른 글

Squarefree Number  (0) 2015.09.08
Empodia (IOI 2004)  (0) 2015.09.06
CCC12 Stage 2 - The Winds of War  (0) 2015.09.01
CCC14 Stage 2 - Werewolf  (0) 2015.09.01
2015.7.3 ~ 2015.7.23 problem solving  (7) 2015.07.14
댓글
공지사항
최근에 올라온 글
Total
Today
Yesterday