가중치 없는 그래프의 인접행렬의 n승을 하면, i행 j열은 i->j로 가는 길이 n인 경로의 개수라는 사실은 알고 계시죠?

그러나 이 문제에선 가중치가 있는데, 그 값이 그리 크지 않습니다. 5 이하네요. 그래프를 변형시켜서 가중치가 없는 그래프로 바꾸면 문제를 풀 수 있어 보입니다.