글 읽기 - 반례가 뭔지 모르겠어요...

tjgy9023 5년 전 0

몇개 올라온거 해봤는데

잘나오는데 어디를 잘못 짠건지..

반례 있을까요 ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class DijkstaMain {

	static int[] dist;
	static int[] path;
	static boolean[] visited;
	public static void main(String[] args) throws IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine())+1;
		int M = Integer.parseInt(br.readLine());
		
		ArrayList<Edge>[] aLists = new ArrayList[N];
		
		dist = new int[N];
		path = new int[N];
		visited = new boolean[N];
		
		for(int i = 0; i < N; i++) {
			dist[i] = Integer.MAX_VALUE;
			path[i] = -1;
			aLists[i] = new ArrayList<>();
		}
		for(int i = 0 ; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			aLists[a].add(new Edge(a, b, w));
		}
		st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		dijkstra(a, aLists);
		System.out.println(dist[b]);
	}
	
	public static void dijkstra(int startVertex, ArrayList<Edge>[] aLists) {
		
		
		PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				// TODO Auto-generated method stub
				return o1.weigth - o2.weigth;
			}
		});
		
		for(Edge edge : aLists[startVertex]) {
			pq.add(edge);
		} //시작
		
		dist[startVertex] = 0;
		path[startVertex] = 0;
		
		
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			int prev = edge.vertex;
			int adj = edge.adj;
			visited[prev] = true;
			
			if(!visited[adj]) {
				int curDist = dist[adj];
				int newDist = dist[prev] + edge.weigth;
				if(newDist < curDist) {
					dist[adj] = newDist;
					path[adj] = prev;
					for(Edge adjEdge : aLists[adj]) {
						pq.add(adjEdge);
					}
				}
			}
		}
		
	}
}


class Edge{
	int vertex,adj,weigth;

	public Edge(int vertex,int adj, int weigth) {
		super();
		this.vertex = vertex;
		this.adj = adj;
		this.weigth = weigth;
	}
	
}

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

문제

문제

출처

ICPC

반례가 뭔지 모르겠어요...

tjgy9023 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말