241 Avoid Your Professor 문제..

  • Stun
    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)
    어디에서 오류에 빠진 걸까요? +_+ 도와주세요

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    9년 전
4개의 댓글이 있습니다.
  • 김민현
    김민현

    플로이드는 쓰지 않아도 되지 않을까요?
    어차피 우선순위큐를 쓰셨다고 하니까, dijkstra 처럼 노드가 pop되는 순간 시작점에서 노드까지 최단경로임이 유지될것 같은데..
    아무튼 redundant 인것 뿐이고... 왜 틀렸는지는 모르겠습니다.
    뭐에대해서 우선순위 큐를 쓰셨는지가 안나와있는데 당연히 시작점에서 가장 가까운 순으로 pop하셨겠죠?


    9년 전 link
  • JongMan
    JongMan

    일단 알고리즘의 골격은 맞고요. 소스코드 보면서 디버그 했네요. -_-; 두 개의 문제가 있습니다. ^^;
    1. 해당 점이 f-t 최단경로 위에 있는지 판단하는 것과 별개로, 간선 (A,B) 가 해당 경로 위에 있을 수 있는지도 평가하셔야 합니다. if 문을 간단히 고치면 되네요. :)
    2. 경로의 수는 2^32 를 넘을 수 있습니다. 사실 2^100 까지 올라갈 수 있어야 하는데 실제로 그런 테스트 케이스는 없습죠. -_-;


    9년 전 link
  • Stun
    Stun

    네 시작점에서 가장 가까운 순으로 pop 하였습니다 ^^ 사실 UVa에 Avoid Boss 인가 (이름이 가물가물하네요^^;) 최단거리가 같은 모든 패스에 대해서 길을 지우는 문제를 풀었던 기억이 있어서 플로이드를 썼는데 없이 풀수도 있나 보군요 ^^


    9년 전 link
  • Stun
    Stun

    -_- 지저분한 소스코드 보시느라 고생하셨겠습니다 ㅠ_ㅠ 감사합니다. 마지막 대회가 끝나고 봐버렸네요 ^^;;;; 아무튼 감사합니다!


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.