안녕하세요, 코드에 몇가지 문제들 보이는 거 같네요.
1. 몇몇 곳에서 integer overflow 일어납니다.
다익스트라 함수에서 파라미터로 전달되는 r값, 21번째 줄에서 y값은 int가 아닌 ll이 되어야 합니다.
(다시 보니 이 문제의 경우 r값은 ll일 필요는 없네요)
2. 33번째 줄 pq.pop(); 을 21번째 줄 바로 밑으로 옮겨주세요. pq에 원소가 추가되면서 pq.top() 원소가 바뀔 수 있습니다.
이렇게 되면 이번에 탐색한 {-y, z} 가 아닌 엉뚱한 원소를 뺄 수 있습니다.
3. if(dis[z]>y) continue; 를 넣으면 더 빨리 시간초과 난다고 하셨는데요, 부등호가 이상합니다.
매번 불필요한 if 조건 검사때문에 더 빨리 시간초과 뜨는거 같네요.
4. 이건 코드 최적화인데요, 중간에 if(z == n) break; 를 넣어보세요 (도착점 도착)

songibusut 1년 전
시간 초과가 계속 납니다. 아무리 봐도 알고리즘 상의 문제는 아닌것 같습니다. 삼분탐색+다익스트라
혹시 이유를 아시는 고수님이 있으면 알려주세요
참고로 다익스트라 중간에 if(dis[z]>y) continue 쓰면 더빨리 시간 초과가 납니다.