그냥 심심풀이로 풀다가 계속 WA 받아서.. 조금 도움을 받아보고자 질문을 해봅니다.


우선 저의 경우는 Floyd 알고리즘을 통해서 모든 최단 경로를 찾으려고 했고요.

[s][e] = [s][k] + [k][e] 에 해당하는 k가 모든 최단 경로 위에있는 점이라 생각했습니다.


문제는 그러한 최단경로가 몇개 있나는 건데요.

함수(func)하나를 선언해서 우선순위큐 탐색을 통해 f, t까지의 경로가지의 수를 세었습니다.

이때 f -> t 까지의 경로가지의 수는  f에서 부터 큐에 넣어가면서 확장해 나갑니다.

큐에서 하나를 꺼내 이어져 있는 점들중 그 점이 f - t 까지의 최단경로 위에 있는 점이라면 (위의식)

가지수[t] += 가지수[f] 를 해주었고 만약 t라는 점이 이미 방문 되지 않았거나 큐에 존재하지 않는다면 큐에 넣는 식으로 구현 했습니다.


그래서 답안인 임의의 n의 점의 확률을 다음과 같은 식으로 구했습니다.


total = func(1, v);

up = func(1, n) * func(n, v);

gcd = GCD(up, total);


(up / gcd) "/" (total / gcd)


어디에서 오류에 빠진 걸까요? +_+ 도와주세요

이 게시물을...