5815번 - HIPERPROSTOR
제가 생각한 방법은 일단 각 행성들사이 경로가 있는 여부만 확인한 뒤,
쿼리가 들어올 때 마다 dfs로 모든 가능한 경로를 찾아 각 경로의 비용을 ax+b꼴로 나타낸 뒤,
x를 계속 증가시키면서 모든 최소비용을 찾는 방법입니다.
0x + b꼴이 하나도 없을 경우 inf를 출력하고, ax+b(a!=0)꼴의 최소값이 0x+b꼴의 최소값을 넘어가면
x를 증가시키며 최소값을 찾는 것을 중단시킵니다.
쿼리는 최대 10개고 x도 커봤자 백만 이하니까 될줄 알았는데, dfs로 모든 가능한 경로를 찾는 부분에서 TLE가 납니다. 이 방법말고 다른 방법이 정해인가요?
저 dfs로 경로를 찾는게 과연 빠를까요?정점이 500개라서 모든 경로를 찾으면 당연히 시간안에 안나올 거 같네요...그리고 소스가 뭔가 이상하네요 minans를 선언하고 바로 출력..?
아 저거 원래 x증가시키면서 도는게 있었는데 그거때문에 TLE나는지 확인한다고 잠시 빼놓은거에요 ㅠ
댓글을 작성하려면 로그인해야 합니다.
wwiiiii 9년 전
제가 생각한 방법은 일단 각 행성들사이 경로가 있는 여부만 확인한 뒤,
쿼리가 들어올 때 마다 dfs로 모든 가능한 경로를 찾아 각 경로의 비용을 ax+b꼴로 나타낸 뒤,
x를 계속 증가시키면서 모든 최소비용을 찾는 방법입니다.
0x + b꼴이 하나도 없을 경우 inf를 출력하고, ax+b(a!=0)꼴의 최소값이 0x+b꼴의 최소값을 넘어가면
x를 증가시키며 최소값을 찾는 것을 중단시킵니다.
쿼리는 최대 10개고 x도 커봤자 백만 이하니까 될줄 알았는데, dfs로 모든 가능한 경로를 찾는 부분에서 TLE가 납니다. 이 방법말고 다른 방법이 정해인가요?