글 읽기 - 다익스트라 틀린부분이 뭔지 모르겠어요..

damoti 4년 전 0

샘플에 있는 답은 맞게 나오는데, 제출했는데 틀렸다고 나와서요...

N^2이 아니라 pq를 이용해서 NlogN으로 풀었는데, 어디서 틀린것인지 혹시 알수있을까요?ㅠㅠㅠ

반례랑 틀린 로직이 무엇인지 궁금합니다.. 부탁드릴게요

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Edge implements Comparable{
int s, e, w;

public Edge(int e, int w) {

this.e = e;
this.w = w;
}

@Override
public int compareTo(Edge e) {
return this.w - e.w;
}
}

public class Main {

static int V, E, K;
static ArrayList[] list;
static int[] dist;
static boolean[] visited;
static int max = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
K = Integer.parseInt(br.readLine()); 
list = new ArrayList[V+1];
dist = new int[V+1];
visited = new boolean[V+1];


for(int i=0; i();
}

for(int i=0; i pq = new PriorityQueue();

dist[k] = 0;

pq.add(new Edge(k, 0));

while(!pq.isEmpty()) {
Edge current = pq.poll();
int now = current.e;
visited[now] = true;

for(int i=0; i dist[now] + cost) {
dist[end] = dist[now] + cost;
visited[end] = true;
pq.add(new Edge(end, dist[end]));
} 
}

}
}
}

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

문제

문제

출처

ICPC

다익스트라 틀린부분이 뭔지 모르겠어요..

damoti 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말