[거의최단경로] 시간초과....lol

[yess98]

[거의 최단 경로 문제]를 풀고 있는데 자꾸 시간초과 문제로 통과를 못하고 있습니다 ㅜㅜ
다익스트라를 돌면서 시간 초과를 방지할 수 있는 조건들은 다 넣어준것 같은데 혹시 빠진 부분이 있는걸까요 ..? 문제 푸신 분들 조언 부탁드립니다 !! :)

제가 작성한 코드는 아래와 같아요 !

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;



public class Main {
	// 거의 최단 경로 
	// 단방향 
	// n = 500, m = 10000 , p = 1000
	// 최단 경로가 없는 경우는 -1 
	
	// 최단 경로 구하기 <다익스트라> // 음수 간선 x 
	static class Line implements Comparable<Line> {
	int target; 
	int cost; 
	public Line(int t, int c ) {
		this.target = t; 
		this.cost = c; 
	}
	public int compareTo(Line e ) {
		return this.cost - e.cost;
	}
}
	static int n ; 
	static int m ; 
	static int start; 
	static int dest; 
	static StringBuilder sb; 
	static ArrayList [] al ; 
	static PriorityQueue<Line> pq ; 
	static int [] dist; 
	static int INF = Integer.MAX_VALUE;
	static ArrayList [] shortestPath; 
	static boolean [][] check ; 
	public static void main(String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
		sb  = new StringBuilder(); 
		while(true) {
		StringTokenizer st = new StringTokenizer(br.readLine()); 
		n = Integer.parseInt(st.nextToken()); 
		m = Integer.parseInt(st.nextToken()); 
		if(n == 0 && m == 0 ) break; 
		st = new StringTokenizer(br.readLine()); 
		start = Integer.parseInt(st.nextToken()); 
		dest = Integer.parseInt(st.nextToken()); 
		al = new ArrayList [n]; 
		shortestPath = new ArrayList [n] ; 
		check = new boolean [n][n]; 
		for(int i = 0 ; i < n ; i ++) {
			al[i] = new ArrayList<Line>(); 
			shortestPath [i] = new ArrayList<Integer>(); 
		}
		for(int i = 0 ; i < m ; i ++) {
			st = new StringTokenizer(br.readLine()); 
			int a = Integer.parseInt(st.nextToken()); 
			int b = Integer.parseInt(st.nextToken()); 
			int c = Integer.parseInt(st.nextToken()); 
			al[a].add(new Line(b,c)); 
		}
		
		dijkstra(start, dest); 
		backtracking(start,dest); 
		dijkstra(start, dest); 
		if(dist[dest] == INF) {
			sb.append(-1 + "\n"); 
		}
		else {
			sb.append(dist[dest] + "\n"); 
		}
	}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	
	
}
// 다익스트라 
	static void dijkstra(int start, int dest) {
		pq = new PriorityQueue<Line>(); 
		dist = new int [n] ; 
        for(int i = 0; i < dist.length; i ++){
            dist[i] = INF; 
        }
		dist[start] = 0 ; 
		pq.add(new Line(start,0 )); 
		while(!pq.isEmpty()) {
			Line out = pq.poll();
            if(out.cost > dist[out.target]) continue; 
			for(int i = 0 ; i < al[out.target].size(); i ++) {
				Line now = (Line) al[out.target].get(i); 
                if(check[out.target][now.target] == true) continue; 
				if(dist[out.target] + now.cost < dist[now.target]) {
					dist[now.target] = dist[out.target] + now.cost; 
					pq.add(new Line(now.target ,dist[now.target]));
					shortestPath[now.target].clear(); 
					shortestPath[now.target].add(out.target); 
				}
				else if(dist[out.target] + now.cost == dist[now.target]) {
					shortestPath[now.target].add(out.target); 
				}
				
			}
	     }
     }
// 최단 경로 간선들 체크 
	static void backtracking(int start, int dest) {
		if(dest == start) {
			return ; 
		}
		int size = shortestPath[dest].size(); 
		for(int i = 0 ; i < size ; i ++) {
			int next = (int) shortestPath[dest].get(i); 
			check[next][dest] = true; 
			backtracking(start,next); 
		}
	}
}

[wjdgns7712]

저랑 같은 문제셨군요..ㅠㅠ

// 최단 경로 간선들 체크 
static void backtracking(int start, int dest) {
  if(dest == start) {
	  return ; 
  }
  int size = shortestPath[dest].size(); 
  for(int i = 0 ; i < size ; i ++) {
    int next = (int) shortestPath[dest].get(i); 
    if(!check[next][dest]){
      check[next][dest] = true; 
      backtracking(start,next); 
    }
  }
}

위와 같이 코드 수정하니 통과되네요

위 그림처럼 동일한 부모에 대해서 반복적으로 backtracking(start, next)를 호출하면서 생기는 문제인것같아요

[wjdgns7712]

// 최단 경로 간선들 체크 
static void backtracking(int start, int dest) {
  if(dest == start) {
      return ; 
  }
  for(int next : shortestPath[dest]) {
    if(!check[next][dest]){
      check[next][dest] = true; 
      backtracking(start,next); 
    }
  }
}

추가로 for each 문으로 처리하면 조금 더 깔끔할거같아요

[yess98]

if(!check[next][dest])라는 조건을 달아주면 불필요한 재귀함수 호출을 막을 수 있어서 시간 절약이 가능하겠네요 !
고맙습니다 정훈님 !