175 - 여행 경로 정하기

  • 음매~@
    음매~@

    문제를 푸는 방법이..
    최단거리 알고리즘을 응용해서, 각 정점가지의 최소/최대 속도를 기록하게 한 뒤, 그 차이의 최소 값을 갱신하는 방식으로는 해를 찾을 수 없나요?
    문제 설명에는 없지만 그림을 보니 정점간의 간선의 개수는 여러개 일 수도있는 것 같아서 그것도 처리했는데, WA네요..
    문제를 잘못 접근 한 걸까요?

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

    15년 전
2개의 댓글이 있습니다.
  • 음매~@
    음매~@

    자답이네요...정점간 간선의 개수가 두개 이상일 경우에는 기본적인 최단거리 알고리즘으로 해를 도출하지 못할거 같네요.. ㅠㅠ


    15년 전 link
  • Toivoa
    Toivoa

    저라면 union-find disjoint set을 이용할 것 같은 문제네요.
    유사문제로 uva에 magic car - http://online-judge.uva.es/p/v104/10457.html 가 있습니다. 'ㅅ'


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