글 읽기 - 만약 노드의 갯수가 적다면

jsh5052 2년 전 0

이와 같이 코드를 짰는데 V가 10000개정도 밖에 받지 않는다 했을 때 이 코드로 구현이 가능한가요?

import java.util.*;

class Main
{
	static int[][] dist;
	static Vector<Integer>[] ans;
	static boolean[] visited;
	public static int treeDiameter(int totalDepth, int cur)
	{
		if(ans[cur].size()==0) return totalDepth;
		
		int ret = totalDepth;
		visited[cur] = true;
		for(int i = 0; i < ans[cur].size(); i++)
		{
			int next = ans[cur].get(i);
			if(visited[next]) continue;
			
			ret = Math.max(ret, treeDiameter(totalDepth+dist[cur][next], next));
		}
		visited[cur] = false;
		return ret;
	}

	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		dist = new int[V+1][V+1];
		ans = (Vector<Integer>[])new Vector[V+1];
		
		for(int i = 1; i <= V; i++)
		{
			ans[i] = new Vector<Integer>();
		}
		visited = new boolean[V+1];
		while(V-->0)
		{
			int cur = sc.nextInt();
			int ansCur = 0;
			int distance = 0;
			while(ansCur!=-1)
			{
				if(ansCur==0)
					ansCur = sc.nextInt();
				
				ans[cur].add(ansCur);
				distance = sc.nextInt();
				dist[cur][ansCur] = distance;
				ansCur = sc.nextInt();
			}
		}
		System.out.println(treeDiameter(0, 1));
	}
}

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

문제

문제

출처

ICPC

만약 노드의 갯수가 적다면

jsh5052 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말