아직 계정이 없으신가요? 회원가입

Dev. Talk

재직자 본선 거리합 구하기 문제, 메모리 및 시간 제한 제시된 것이랑 다른거 같습니다.

회원사진zaza1994
100 views2021-11-10 20:47

1초, 1000MB 쯤에서 끝나는 것 같은데,

문제에서는 Java 6초 2024MB로 나와있어서요.


import java.util.*;
import java.io.*;


public class Main
{
  static int N;
	static int[][] map;
	static long[][] dp;
	static Node[] nodes;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N+1][N+1];
		dp = new long[N+1][N+1];
		nodes = new Node[N+1];
		for(int n = 1; n < N+1; n++) nodes[n] = new Node(n);
		StringTokenizer st;
		for(int n = 0; n < N-1; n++) {
			st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			map[n1][n2] = c;
			map[n2][n1] = c;
			nodes[n1].adj.add(n2);
			nodes[n2].adj.add(n1);
		}
		makeTree(1,-1);
		fillTree();

		for(int i = 1; i < N+1; i++) {
			long sum = 0;
			for(int j = 1; j < N+1; j++) {
				if(i!=j) sum += dp[i][j];
			}
			System.out.println(sum);
		}
	}
	static void fillTree() {
		
		for(int i = 2; i < N+1; i++) {
			for(int j = 2; j < N+1; j++) {
				if(i != j && dp[i][j] == 0) {
					int k = nodes[i].parent;
					while(dp[k][j] == 0) {
						k = nodes[k].parent;
					}
					dp[i][j] = dp[i][k] + dp[k][j];
					dp[j][i] = dp[i][j];
					// System.out.println(String.format("%d --> %d : using %d ==> %d", i, j ,k, dp[i][j]));
				}
			}
		}
		
		
	}
	
	
	static void makeTree(int idx, int prv) {
		nodes[idx].parent = prv;
		
		int ppdx = prv;
		int pdx = idx;
		long cost = 0; 
		while(ppdx != -1) {
			cost += map[pdx][ppdx];
			dp[ppdx][idx] = cost;
			dp[idx][ppdx] = cost;
			// System.out.println(String.format("%d --> %d : %d", ppdx, idx, cost));
			pdx = ppdx;
			ppdx = nodes[ppdx].parent;
		}
		
		
		for(int p : nodes[idx].adj) {
			if(p != prv) {
				makeTree(p, idx);
			}
		}
	}
	
	static class Node{
		int parent, num;
		LinkedList<Integer> adj;
		Node(int num) {
			this.num = num;
			adj = new LinkedList<Integer>();
		}
	}

}



아니면 제가 코드가 문제가 있어서 런타임에러가 나는 것인가요?