글 읽기 - 데이터 추가해주세요!!

zzaa9898 6년 전 0

4 3

1 1 10 1

1 2

2 4

3 4

11을 출력하는 코드

3을 출력하는 코드

모두 정답처리됩니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BJ1005 {
	static int T;
	static StringBuffer sb;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		sb = new StringBuffer();
		T = sc.nextInt();
		
		while(T-- > 0) {
			int n = sc.nextInt();
			int k = sc.nextInt();
			int arr[] = new int[n+1];
			int indegree[] = new int[n+1];
			int adjMap[][] = new int[n+1][n+1];
			
			for(int i=1; i<n+1; i++)
				arr[i] = sc.nextInt();
			for(int i=0; i<k; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				adjMap[x][y] = 1;
				indegree[y]++;
			}
			
			int target = sc.nextInt();
			sb.append(pathSearch(adjMap, indegree, arr, target)+"\n");
			
			
		}
		System.out.print(sb.toString());
		
	};
	
	static int pathSearch(int[][] adjMap, int[] indegree, int[] arr, int target) {
		int result[] = new int[arr.length];
		Queue<Integer> q = new LinkedList<>();
		
		for(int i=1; i<arr.length; i++) {
			if(indegree[i] == 0) {
				q.add(i);
				result[i] = arr[i];
				/* 다음과 같이 indegree 배열 해당 인덱스의 값이
				 *  0 일 경우 큐에 추가하는 코드 입니다.
				 *  break 의 유무에 따라 해당 TC가 3 혹은 11을
				 *  출력하는데 두 코드 모두 정답처리됩니다.
				 */
			}
		}
		
		while(!q.isEmpty()) {
			int temp = q.poll();
			for(int i=1; i<arr.length; i++) {
				if(adjMap[temp][i] == 1) {
					result[i] = result[i] > result[temp]+arr[i] ? result[i] : result[temp] + arr[i];
			
					if(--indegree[i] ==0)
						q.add(i);
				}
			}
		}
		return result[target];
	}

}

startlink 6년 전 0

데이터 추가했습니다.

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

문제

문제

출처

ICPC

데이터 추가해주세요!!

zzaa9898 6년 전 0

startlink 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말