[editorial] ACM-ICPC 2008 Seoul Regional Problem C - Homing (2)

  • Being
    Being
    [03:52] <Being> ㅜㅜ
    [03:52] <JongMan> 헐
    [03:52] <Being> 새글로 쓸까
    [03:52] <Being> ..
    [03:52] <JongMan> 난 달아진다
    [03:52] <JongMan> ..
    [03:52] <Being> 전 IE도 크롬도 안되는듯
    [03:52] <Being> ㅠ
    [03:53] <Being> C번 문제 에디토리얼에 달아지나여?
    [03:53] <Being> 딴데는 저도 되네여
    [03:53] <JongMan> 나 달았자네
    [03:53] <Being> 태님 에디토리얼에 무슨짓을
    [03:53] <Being> -_-;;;;;;;;;;;
    [03:53] <JongMan> ㅋㅋㅋㅋㅋㅋ
    [03:53] <JongMan> 새 글로 써줘
    [03:53] <Being> 음?!
    [03:53] <Being> 딴데는 저도 되는데
    [03:53] <Being> 뭐지...
    [03:54] <Being> 저주받은듯ㅋ

    이렇게 되어 새 글로 쓰게 되었는데, 계속 글이 안올라가서 고치면서 확인해보니 글 어딘가에 ^B 문자가 포함되어 있더군요....너 어디서 온거니...
    O(VE) 시간에 이 문제를 풀어 봅시다. VE10,000이니 O(V^2 log E) 보다야 빠르겠지요.
    아이디어는:

  • 시점과 종점을 (s, e)라 하고 e로부터의 최단거리 트리를 생각한다.

  • 어떤 최단거리를 이루는 엣지 하나를 끊으면(끊은 엣지를 (p, q)라 하자), 이미 만들어졌던 e로부터의 최단거리 트리가 반토막이 나면서 두 트리가 생긴다.

  • 당연히 그 두 트리를 잇는 엣지들만이 최단거리를 구성할 수 있다.
  • 출발점 쪽의 트리의 경우 끊어진 점이 루트, 도착점 쪽의 트리의 경우 도착점이 루트이므로 (x, y)가 두 트리를 잇는 엣지라 하면 s -> p -> x -> y -> e 의 경로를 선택해야 하는데, 이 비용은:
    • s -> p := dist(e, s) - dist(e, p)
    • p -> x := dist(e, x) - dist(e, p)
    • x -> y := weight(x, y)
    • y -> e := dist(e, y) 와 같이 쉽게 계산할 수 있다.

    그래서, 끝점으로부터의 최단거리 트리를 구하고(다익스트라 등을 사용하면 어디로부터 왔는지 기록하면 바로 구할 수 있겠죠) 최단거리를 구성하는 엣지들을 하나씩 잘라 보면서 트리를 두동강내고, E개의 엣지들을 모두 보면서 두 트리를 잇는지 확인하고, 잇는 경우 그 엣지를 선택하여 되돌아가는 거리를 쉽게 계산할 수 있으니 O(VE) 에 해결할 수 있습니다.
    페이퍼를 찾아보실 분은 "Real Time Critical Edge of the Shortest Path in Transportation Networks, Yinfeng Xu and Huahai Yan, 2006" 을 보시면 되겠습니다. (별 새로운 이야기는 없어요)

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

    15년 전
1개의 댓글이 있습니다.
  • VOCList
    VOCList

    이 기세로 I도 헤헤


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