글 읽기 - 시간초과에 대해서 질문합니다.

naegeora 7년 전 0

아래 알고리즘 처러 위상정렬순서로 돌면서 각 정점의 earliest 를 구하고,

역위상 정렬 순서로 돌면서 각 정점의 latest를 구한 후.

각 간선에 대하여

early(x,y)=earliest(x)

late(x,y)=latest(y)-weight(x,y) 구한다.

if(early(x,y)==late(x,y)) 이면 임계경로이다.

아래 로직대로 하면 O(V^2) 2초내로 끝날거 같은데 시간초과 나오네요...

뭐가 잘못된 걸까요? 인접리스트구현을 다르게 해야 하나요?

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Scanner;


public class Main {

	static ArrayDeque<Integer> quetemp = new ArrayDeque<Integer>();
	static ArrayDeque<Integer> queseq = new ArrayDeque<Integer>();

	static ArrayList<Integer>[] list=new ArrayList[10001];
	static int[] indegree,outdegree,earliest,latest;
	static int V,E,Start,End;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		V=sc.nextInt(); E=sc.nextInt();

		for(int i=1;i<=V;i++) {
			list[i]=new ArrayList<Integer>();	
		}
		for(int i=0;i<E;i++){
			int a= sc.nextInt();
			int b= sc.nextInt();
			int c= sc.nextInt();
			list[a].add(b); list[a].add(c); 
		}

		Start=sc.nextInt(); End=sc.nextInt();

		CriticalActivity_forward();

		int initial=0;

		for(int i=Start;i<=End;i++){ //출발지점에서 도착지점까지 최대 일수 구함. 중간에 나올수도 있음.
			if(initial<earliest[i])initial=earliest[i];
		}

		CriticalActivity_backward(initial);
		
		int counter=0;
		for(int i=1;i<=V;i++){
			if(list[i]!=null){
				for(int j=0;j<list[i].size()-1;j+=2){
					int childvertex=list[i].get(j);
					int cost=list[i].get(j+1);
					int e=earliest[i];
					int l=latest[childvertex]-cost;
					if(l==e&&cost!=0)
						counter++;

				}
			}
		}
		
		System.out.println(initial);
		System.out.println(counter);
	}

	public static void CriticalActivity_forward() {
		// TODO Auto-generated method stub

		indegree=new int[V+1]; earliest=new int[V+1];
		for(int i=1;i<=V;i++) {
			indegree[i]=0;earliest[i]=0;
		}
		for (int i=1;i<=V; i++){ //모든 정점에 대해서 indegree 추가
			if(list[i]!=null){
				for(int j=0;j<list[i].size()-1;j+=2){
					int childvertex=list[i].get(j);
					indegree[childvertex]++;
				}
			}
		}
		for (int i=1;i<=V; i++){ //Root 추가함.
			if(indegree[i]==0)quetemp.addLast(i);
		}

		while(!quetemp.isEmpty()){		//모든 정점 que가 비면 DAG가 아님(순환이 있음)
			int vertex=quetemp.pollFirst();
			//queseq.add(vertex);
			for(int i=0;i<list[vertex].size()-1;i+=2){
				int childvertex=list[vertex].get(i);
				int cost=list[vertex].get(i+1);
				indegree[childvertex]--;
				if(indegree[childvertex]==0)quetemp.addLast(childvertex);
				if(earliest[childvertex] < earliest[vertex]+cost) 
					earliest[childvertex] = earliest[vertex]+cost;
			}
		}



	}
	public static void CriticalActivity_backward(int initial) {
		// TODO Auto-generated method stub
		outdegree=new int[V+1]; latest=new int[V+1];

		for(int i=1;i<=V;i++) {
			outdegree[i]=0; latest[i]=initial;
		}

		for (int i=1;i<=V; i++){ //모든 정점에 대해서 outdegree 추가
			if(list[i]!=null){
				outdegree[i]=list[i].size()/2;
			}
		}

		for (int i=1;i<=V; i++){ //endpoint que에 추가함.
			if(outdegree[i]==0)quetemp.addLast(i);
		}
		while(!quetemp.isEmpty()){ 
			//que가 비면 DAG가 아님(순환이 있음)
			int a=quetemp.pollFirst();
			//queseq.add(a);
			for(int i=1;i<=V;i++){
				for(int j=0; j<list[i].size()-1;j+=2){
					int childvertex=list[i].get(j);
					int cost=list[i].get(j+1);
					if(childvertex==a){
						outdegree[i]--;
						if(outdegree[i]==0)quetemp.addLast(i);
						if(latest[i] >latest[childvertex]-cost )
							latest[i] = latest[childvertex]-cost;
					}
				}
			}
		}

	}

}

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

문제

문제

출처

ICPC

시간초과에 대해서 질문합니다.

naegeora 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말