글 읽기 - 우선순위큐 사용 다익스트라 시간초과가 나요

naegeora 7년 전 1

우선순위큐 사용 다익스트라 시간초과가 나요

오랜시간 고민했는데...해결아 안되네요...

예제케이스 맞게 나오고 다른 다익스타 문제 1916번도 맞게 나오는데

이문제는 시간초과로 뜨네요....어디를 어떻게 고치면 좋을까요?

좀 도와주십시요..2

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;


class Main {
	static int INF = 987654321;
	static int[] dist;  //start node부터 i node까지의 누적최단거리
	static boolean[] visited ;// 각 노드별로 방문한 적이 있는지 표시
	static int[] parent;        // 각노드의 이전 노드번호
	static int N ,M,S,E;
	static PriorityQueue<Element> pq = new  PriorityQueue<Element>();
	static int[][] edge;


	static class Element implements Comparable<Element>{
		private int Vertex;
		private int distance;

		public Element(int Vertex, int distance){
			this.Vertex = Vertex;
			this.distance = distance;
		}
		public int compareTo(Element o){
			return distance - o.distance;
		}
	}

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("res/Dijkstra_1_baekjun1753.txt"));
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt(); M=sc.nextInt(); S=sc.nextInt();
		dist = new int[N+1];
		edge=new int[M+1][3];
		visited= new boolean[N+1];
		parent = new int[N+1];
		for(int i=0;i<M;i++){
			int A=sc.nextInt(); int B=sc.nextInt();int C=sc.nextInt();
			edge[i][0]=A;
			edge[i][1]=B;
			edge[i][2]=C;
		}
		Arrays.fill(dist, INF);
		Arrays.fill(visited, false);
		Arrays.fill(parent, S);//이전 node start 노드로 초기화

		dist[S] = 0;

		shortestPath(S);

		for(int i=1;i<=N;i++){
			if(dist[i]==INF)System.out.println("INF");
			else System.out.println(dist[i]);
		}
		sc.close();

	}
	public static void shortestPath(int start){
		pq.add(new Element(start, dist[start]));

		while(!pq.isEmpty()){
			int distance = pq.peek().distance;
			int here = pq.peek().Vertex;
			pq.poll();
			visited[here]=true;

			if(distance > dist[here]) //하위 경로중 이미 업데이트 된것
				continue;

			for(int i = 0; i < M; i++){//하위인접트리 돌면서 최소경로 갱신하고
				int from=edge[i][0];
				int to=edge[i][1];
				int cost=edge[i][2];
				if(visited[to]==false&&from==here && dist[to] > dist[here] + cost){
					dist[to] = dist[here] + cost;
					parent[to] = here;    // 최소경로를 제공하는 전노드
					pq.add(new Element(to, dist[to])); //방문한 하위트리 노드를 pq에 넣어줌
				}
			}
		}
	}
}

etaehyun4 7년 전 0

here에서 나가는 edge들을 모든 엣지중에서 찾으셨는데, 인접 리스트를 통해 그 엣지들만 돌 수 있게 하면 좋을 듯 합니다

naegeora 7년 전 0

etaehyun4 님 답변 감사합니다..
아래 조건에서 from==here 조건에서 가지치기 되면 계산수는 같지않나요?

if(visited[to]==false&&from==here && dist[to] > dist[here] + cost)

만약 인접리스트로 할 경우 가중치를 어디다가 저장하나요?

예를 들어서 edge[3]={4,5,6} 일경우....?

naegeora 7년 전 0

etaehyun4 님 답변 너무 감사합니다..

님 말대로 인접리스트 써서 했더니 맞았습니다.

님 언제 사이다 한병 대접하죠...

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

문제

문제

출처

ICPC

우선순위큐 사용 다익스트라 시간초과가 나요

naegeora 7년 전 1

etaehyun4 7년 전 0

naegeora 7년 전 0

naegeora 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말