글 읽기 - 어떤부분에서 틀렸을까요?

yih9329 5년 전 0

30퍼쯤에서 틀리다고 나옵니다.

어디서 잘못됐을까요?

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Edge implements Comparable<Edge>{
	
	private int fromV;
	private int toV;
	private int weight;
	
	Edge(int fV, int tV, int w){
		fromV = fV;
		toV = tV;
		weight = w;
	}
	
	public int GetStartV() {
		return fromV;
	}
	
	public int GetEndV() {
		return toV;
	}
	
	public int GetWeight() {
		return weight;
	}
	
	public void ChangeWeight(int w) {
		weight = w;
	}

	@Override
	public int compareTo(Edge o) {
		return this.weight - o.weight;
	}
}

class Graph{
	private int numV;
	private int numE;
	private LinkedList<Edge>[] adjList;
	
	Graph(int V, int E){
		numV=V;
		numE=E;
		adjList = new LinkedList[numV];
		for(int i=0; i<numV; i++)
			adjList[i] = new LinkedList<>();
	}
	
	public void AddEdge(Edge e) {
		adjList[e.GetStartV()-1].add(e);
	}
	
	public LinkedList<Edge>[] GetAdjList(){
		return adjList;
	}
	
	
}

public class Main {
	static Graph pg;
	public enum color {black, grey, white};
	static color[] visit;
	static int[] distance;
	
	public static void main(String[] args) {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			StringTokenizer str = new StringTokenizer(br.readLine(), " ");
			int numV = Integer.parseInt(str.nextToken());
			int numE = Integer.parseInt(str.nextToken());
			int startV = Integer.parseInt(br.readLine());
			
			pg = new Graph(numV, numE);
			visit = new color[numV+1];
			distance = new int[numV+1];
			Arrays.fill(visit, color.white);
			Arrays.fill(distance, Integer.MAX_VALUE);
			distance[0] = 0;
			
			for(int i=0; i<numE; i++) {
				str = new StringTokenizer(br.readLine(), " ");
				Edge e = new Edge(Integer.parseInt(str.nextToken()), Integer.parseInt(str.nextToken()), Integer.parseInt(str.nextToken()));
				pg.AddEdge(e);
			}
	
			Dijkstra(startV);
			
			for(int i=1; i<=numV; i++) {
				if(distance[i] == Integer.MAX_VALUE)
					bw.write("INF\n");
				else
					bw.write(Integer.toString(distance[i]) + "\n");
			}
			
			bw.flush();
			bw.close();
			br.close();
		} catch (NumberFormatException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	public static void Dijkstra(int startV) {
		
		visit[0] = color.black;
		distance[startV] = 0;
		LinkedList<Edge>[] adjList = pg.GetAdjList();
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		int curV = startV;
		
		while(true) {
			if(visit[curV] != color.black) {
				visit[curV] = color.grey;
				for(int i=0; i<adjList[curV-1].size(); i++)
					if(visit[adjList[curV-1].get(i).GetEndV()] != color.black) {
						pq.offer(adjList[curV-1].get(i));
						distance[adjList[curV-1].get(i).GetEndV()] = Math.min(distance[adjList[curV-1].get(i).GetEndV()], distance[adjList[curV-1].get(i).GetStartV()]+adjList[curV-1].get(i).GetWeight());
					}
				visit[curV] = color.black;
			}
			
			if(pq.isEmpty())
				break;
			
			curV = pq.poll().GetEndV();
		}
	}
	
}

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

문제

문제

출처

ICPC

어떤부분에서 틀렸을까요?

yih9329 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말