그냥 심심풀이로 풀다가 계속 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)
어디에서 오류에 빠진 걸까요? +_+ 도와주세요
플로이드는 쓰지 않아도 되지 않을까요?
어차피 우선순위큐를 쓰셨다고 하니까, dijkstra 처럼 노드가 pop되는 순간 시작점에서 노드까지 최단경로임이 유지될것 같은데..
아무튼 redundant 인것 뿐이고... 왜 틀렸는지는 모르겠습니다.
뭐에대해서 우선순위 큐를 쓰셨는지가 안나와있는데 당연히 시작점에서 가장 가까운 순으로 pop하셨겠죠?
일단 알고리즘의 골격은 맞고요. 소스코드 보면서 디버그 했네요. -_-; 두 개의 문제가 있습니다. ^^;
1. 해당 점이 f-t 최단경로 위에 있는지 판단하는 것과 별개로, 간선 (A,B) 가 해당 경로 위에 있을 수 있는지도 평가하셔야 합니다. if 문을 간단히 고치면 되네요. :)
2. 경로의 수는 2^32 를 넘을 수 있습니다. 사실 2^100 까지 올라갈 수 있어야 하는데 실제로 그런 테스트 케이스는 없습죠. -_-;
Stun
그냥 심심풀이로 풀다가 계속 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)
어디에서 오류에 빠진 걸까요? +_+ 도와주세요
15년 전