1865번 - 웜홀
1. 플로이드 워셜로 모든 정점 쌍 사이의 최단거리를 구한다
2. 웜홀을 a, b, t로 받았을 때
2-1. b에서 a로 가는 최단거리가 t보다 작으면 YES
2-2. 그런 경우가 없으면 NO
3. 반복
의 논리로 했습니다만 30% 언저리에서 틀렸습니다가 뜨네요.
논리에 오류가 있는지, 구현에 오류가 있는지 잘 모르겠습니다.
아래는 제 코드입니다.
음 수정했더라도 시간초과가 나지 않을까요? 보통 n제한이 400까지는 플로이드로 가능한걸루 알고잇는디 5개의 테케에 500이면 위험한것 같습니다
설령 시간초과가 되더라도 지금은 '틀렸습니다'의 원인을 알고 싶습니다
음 .. 음수간선을 플로이드에서 제외하신건가요? 맞다면 이유가 무엇인지요
1. 도로가 1, 3번 지점을 연결하고 웜홀이 3->2, 2->1로 가는 형태의 음수 사이클을 찾아내지 못할 것 같습니다.
2. 출발지점으로 돌아올 수 있는지가 중요합니다. 그러므로 4->5의 최단거리가 3, 5->4로 가는 웜홀의 t가 4이면 음수사이클이지만,
출발위치(ex. 1번 지점)에서 4번이나 5번 지점에 도달할 수 없다면 의미가 없습니다.
반례입니다.
13 1 21 2 102 3 13 1 100
답변 감사드립니다
댓글을 작성하려면 로그인해야 합니다.
playsworld16 3년 전
1. 플로이드 워셜로 모든 정점 쌍 사이의 최단거리를 구한다
2. 웜홀을 a, b, t로 받았을 때
2-1. b에서 a로 가는 최단거리가 t보다 작으면 YES
2-2. 그런 경우가 없으면 NO
3. 반복
의 논리로 했습니다만 30% 언저리에서 틀렸습니다가 뜨네요.
논리에 오류가 있는지, 구현에 오류가 있는지 잘 모르겠습니다.
아래는 제 코드입니다.