wwiiiii   9년 전

제가 생각한 방법은 일단 각 행성들사이 경로가 있는 여부만 확인한 뒤,

쿼리가 들어올 때 마다 dfs로 모든 가능한 경로를 찾아 각 경로의 비용을 ax+b꼴로 나타낸 뒤,

x를 계속 증가시키면서 모든 최소비용을 찾는 방법입니다.

0x + b꼴이 하나도 없을 경우 inf를 출력하고, ax+b(a!=0)꼴의 최소값이 0x+b꼴의 최소값을 넘어가면

x를 증가시키며 최소값을 찾는 것을 중단시킵니다.

쿼리는 최대 10개고 x도 커봤자 백만 이하니까 될줄 알았는데, dfs로 모든 가능한 경로를 찾는 부분에서 TLE가 납니다. 이 방법말고 다른 방법이 정해인가요?

august14   9년 전

저 dfs로 경로를 찾는게 과연 빠를까요?
정점이 500개라서 모든 경로를 찾으면 당연히 시간안에 안나올 거 같네요...

그리고 소스가 뭔가 이상하네요 minans를 선언하고 바로 출력..?

wwiiiii   9년 전

아 저거 원래 x증가시키면서 도는게 있었는데 그거때문에 TLE나는지 확인한다고 잠시 빼놓은거에요 ㅠ

댓글을 작성하려면 로그인해야 합니다.