fork download
copy 
  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3. import java.util.Scanner;
  4.  
  5. public class Main {
  6. 	static int []건설시간;
  7. 	static int []자식수;
  8. 	static LinkedList<Integer> []건설순서;
  9. 	static int [] result;
  10.  
  11. 	@SuppressWarnings("unchecked")
  12. 	public static void main(String[] args) {
  13.  
  14. 		Scanner sc = new Scanner(System.in);
  15. 		int T = sc.nextInt();
  16. 		for(int i=0;i<T;i++) //테스트 케이스 반복
  17. 		{
  18. 			int N=sc.nextInt();
  19. 			int K=sc.nextInt();
  20. 			건설시간 = new int [N+1];
  21. 			for(int x=1;x<N+1;x++)
  22. 				건설시간[x]=sc.nextInt();
  23. 			건설순서 = new LinkedList[K+1]; 
  24. 			자식수 = new int [N+1];
  25. 			 result = new int [N+1];
  26. 			for(int z=1;z<N+1;z++)
  27. 				건설순서[z] = new LinkedList<Integer>();
  28. 			for(int j=0;j<K;j++)
  29. 			{
  30. 				int c=sc.nextInt(); 
  31. 				int p=sc.nextInt(); 
  32. 				건설순서[c].add(p);   //c를 지어야 p를 건설가능
  33. 				자식수[p]++;
  34. 			} 
  35.  			int W=sc.nextInt();			
  36.  
  37.  			System.out.println(위상정렬(N,K,W));
  38.  
  39. 		}
  40.  
  41. 	}
  42. 	public static int 위상정렬(int N,int K,int W) {
  43. 		Queue<Integer> q = new LinkedList<>();	
  44. 		for(int i=1;i<N+1;i++) //먼저 자식이 없는 노드부터 큐에 삽입한다
  45. 		{ 
  46. 			if(자식수[i]==0)
  47. 			{
  48. 				q.offer(i);
  49. 				result[i]=건설시간[i];
  50. 			}
  51. 		}
  52. 		while(!q.isEmpty()) //큐가 빌때까지 반복 
  53. 		{
  54.  
  55. 			int x =q.poll(); 
  56. 			for(int node : 건설순서[x]) //x 자식             node 부모
  57. 			{
  58. 				result[node] = Integer.max(result[node],result[x]+건설시간[node]);
  59. 				자식수[node]--;
  60. 				if(자식수[node]==0)
  61. 				{
  62. 					q.offer(node);
  63. 				}
  64. 			}
  65.  
  66. 		}
  67.  
  68. 		return result[W];
  69.  
  70.  
  71. 	}
  72. }
  73.  
Runtime error #stdin #stdout #stderr 0.12s 29524KB
comments (?)
stdin
copy 
1
2 1
1 1
2 1
1
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2
	at Main.main(Main.java:27)
https://ideone.com/4MDt70
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!