글 읽기 - 다익스트라 질문

yih9329 5년 전 0

다익스트라로 구현을 했는데 시간초과가 납니다

어떤 부분에서 시간초과가 난걸까요?

도움주시면 감사드리겠습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

class Info{
	int dest;
	int cost;
	
	Info(int d, int c){
		dest = d;
		cost = c;
	}
}

enum Status {black, gray, white};

public class Main{
	static List<Info>[] bus;
	static int[] d;
	static Status[] visit;
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int n = Integer.parseInt(br.readLine());
			int m = Integer.parseInt(br.readLine());
			bus = new LinkedList[n+1];
			visit = new Status[n+1];
			d = new int[n+1];
			
			for(int i=1; i<=n; i++)
				bus[i] = new LinkedList<>();
			
			for(int i=0; i<m; i++) {
				String[] s = br.readLine().split(" ");
				int f = Integer.parseInt(s[0]);
				int t = Integer.parseInt(s[1]);
				int c = Integer.parseInt(s[2]);
				bus[f].add(new Info(t,c));
			}
			
			for(int i=1; i<=n; i++) {
				
				Dijkstra(i);
				for(int j=1; j<=n; j++) {
					if(d[j] == Integer.MAX_VALUE)
						bw.write("0 ");
					else
						bw.write(Integer.toString(d[j]) + " ");
				}
				
				bw.write("\n");
			}
			bw.close();
			br.close();
			
		} catch(IOException e) {
			e.printStackTrace();
		}
	}
	
	static void Dijkstra(int start) {
		
		Arrays.fill(d, Integer.MAX_VALUE);
		Arrays.fill(visit, Status.white);
		PriorityQueue<Info> q = new PriorityQueue<>((a,b) -> (a.cost - b.cost));
		int cur = start;
		d[start] = 0;
		
		while(true) {
			visit[cur] = Status.gray;
			for(int i=0; i<bus[cur].size(); i++) {
				int nc = bus[cur].get(i).dest;
				int cost = bus[cur].get(i).cost;
				
				if(visit[nc] == Status.white) {
					q.offer(new Info(nc, d[cur]+cost));
					d[nc] = Math.min(d[nc], d[cur] + cost);
				}
			}
			visit[cur] = Status.black;
			if(q.isEmpty())
				break;
			
			while(true) {                                    // 이미 방문된 노드는 큐에서 제거
				cur = q.poll().dest;
				if(visit[cur] == Status.white)
					break;
				
				if(q.isEmpty())
					return;
			}
		}
	}
}

djm03178 5년 전 1

문제 이름이 플로이드인데 다익스트라로 풀려고 하셔서 그렇습니다. 플로이드 와샬 알고리즘에 대해 공부해 보세요.

참고로 이 문제는 제한상 다익스트라 알고리즘으로 푸는 것이 가능은 하지만, 지금처럼 모든 간선을 저장해서는 매우 비효율적입니다. 다익스트라 알고리즘의 시간복잡도가 O(ElogE)인데, 이를 V번 돌리니 약 1000만log10만 정도나 됩니다. 잘 생각해 보시면 n^2개 이상의 간선을 저장할 필요가 없습니다.

yih9329 5년 전 0

답변 감사드립니다 ^^

다시 한번 생각해봐야겠네요

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

문제

문제

출처

ICPC

다익스트라 질문

yih9329 5년 전 0

djm03178 5년 전 1

yih9329 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말