글 읽기 - 틀렸습니다...

ddd7693 4년 전 0

60퍼 까지는 넘어가는데 틀렷습니다가 뜨네요 ;;

살려주세요~~

공지사항에 몇퍼까지 맞은거 올리지 말라고 봣는데 ;; 도저히 모르겟어서 도움 요청합니다 ㅠ

질문게시판에 있는 in.txt(정점:2만개 간선:19999개) 파일 넣으니까 로컬에서는 결과값 잘 나와요..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;


class Main{
	static class V{
		int det;
		int val;
		public V(int det, int val) {
			super();
			this.det = det;
			this.val = val;
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		int n=Integer.parseInt(stk.nextToken());
		int m=Integer.parseInt(stk.nextToken());
		int st=Integer.parseInt(br.readLine());
		
		int dist[] = new int[n+1];
		int visited[] = new int[n+1];
		
		ArrayList<V>[] list=new ArrayList[n+1];
		for (int i = 0; i < list.length; i++) {
			list[i] = new ArrayList<V>();
		}
		
		for (int i = 0; i < m; i++) {
			stk=new StringTokenizer(br.readLine());
			list[Integer.parseInt(stk.nextToken())].add(new V(Integer.parseInt(stk.nextToken()),Integer.parseInt(stk.nextToken())));
		}
		for (int i = 1; i < n+1; i++) {
			dist[i]=987654321;
		}
		for (int i = 0; i < list[st].size(); i++) {
			int det = list[st].get(i).det;
			int val = list[st].get(i).val;
			dist[det]=val;
		}
		dist[st]=0;
		visited[st]=1;
		for (int i =0 ; i < n-1 ; i++) {
			int min_index=st;
			int min=987654321;
			for (int j = 1; j < n+1; j++) {
				if(visited[j]!=1 && min > dist[j]) {
					min=dist[j];
					min_index=j;
				}
			}
			for (int j = 0; j < list[min_index].size(); j++) {
				int det = list[min_index].get(j).det;
				int val = list[min_index].get(j).val;
				if(visited[det]==0 &&dist[min_index]+val<dist[det])
					dist[det]=dist[min_index]+val;
			}
			visited[min_index]=1;
			
		}
		for (int i = 1; i < n+1; i++) {
			if(dist[i]==987654321)
				System.out.println("INF");
			else {
				System.out.println(dist[i]);				
			}
		}
	}
}

djm03178 4년 전 2

반례입니다.

http://ideone.com/BXz0pV

ddd7693 4년 전 0

감사합니다;ㅠㅠ 넣을때 똑같은 정저의 간선을 계속 최소값으로 갱신해주거나

정점을 하나씩 선택하기 전에 우선순위큐를 써야 겟네요

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

문제

문제

출처

ICPC

틀렸습니다...

ddd7693 4년 전 0

djm03178 4년 전 2

ddd7693 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말