글 읽기 - 다익스트라로 풀었는데 좀 봐주세요

shpre1236 5년 전 0

solve()만 보시면 될거 같아요.

후보군을 만들어놓고 그 안에서 제일 값이 큰거를 계속 뽑아서

현재까지 옮겨진 최대치, i로 옮길수 있는 최대치를 비교해서 i 값을 계속 업데이트 했습니다.

업데이트 될때마다 후보군에 추가해주었고요.

이런식으로 풀어서 대부분 다 ac받았는데 막상 돌리면 틀렸다고 나오네요.

뭐가 문제일까요.

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

public class Main{
	static int N, M;
	static int[][] data;
	static int start, end;
	static boolean[] visit;
	static int[] result;
	static PriorityQueue<Wrapper> q;
	
	static class Wrapper implements Comparable<Wrapper>{
		int index;
		
		Wrapper(int i){
			this.index = i;
		}
		public int compareTo(Wrapper w){
			return (result[this.index] < result[w.index] ? 1 : (result[this.index] == result[w.index] ? 0 : -1));
		}
		
		public boolean equals(Object o){
			return (this.index == ((Wrapper)o).index);
		}
	}
	
	public static void main(String[] args){
		input();
		solve();
	}
	
	static void solve(){
		visit = new boolean[N+1];
		result = new int[N+1];
		result[start] = Integer.MAX_VALUE;
		
		if(N == 1){
			System.out.println(data[1][1]);
			return;
		}
		
		q = new PriorityQueue<Wrapper>();
		q.add(new Wrapper(start));
		
		while(!q.isEmpty()){
			int now = q.remove().index;
			
			visit[now] = true;
			if(now == end){
				System.out.println(result[now]);
				return;
			}
			
			for(int i=1; i<=N; i++){
				if(!visit[i] && data[now][i] != 0){
					if(result[i] < Math.min(result[now], data[now][i])){
						result[i] = Math.min(result[now], data[now][i]);
						if(!q.contains(new Wrapper(i)))	q.add(new Wrapper(i));
					}
				}
			}
		}
		
		System.out.println(result[end]);
	}
	
	static void input(){
		BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
		try{
			StringTokenizer line = new StringTokenizer(buf.readLine());
			N = Integer.parseInt(line.nextToken());
			M = Integer.parseInt(line.nextToken());
			
			data = new int[N+1][N+1];
			for(int i=0; i<M; i++){
				line = new StringTokenizer(buf.readLine());
				int s = Integer.parseInt(line.nextToken());
				int e = Integer.parseInt(line.nextToken());
				data[s][e] = data[e][s] = Math.max(data[e][s], Integer.parseInt(line.nextToken()));
			}
			
			line = new StringTokenizer(buf.readLine());
			start = Integer.parseInt(line.nextToken());
			end = Integer.parseInt(line.nextToken());
		}
		catch(Exception e){}
	}
}

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

문제

문제

출처

ICPC

다익스트라로 풀었는데 좀 봐주세요

shpre1236 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말