글 읽기 - 다익스트라를 반복해서 답을 구하는데 어디가 틀렸는지 모르겠습니다.

jeongyong95 3년 전 0

매 테스트 케이스 다익스트라에서 친구의 수만큼 친구의 위치를 시작점으로 탐색을 시도했습니다.

다익스트라의 answerArr에 각 친구의 시작점 기준으로 distance를 누적해서 가장 작은 거리의 방을 선택하고, 거리가 같으면 작은 번호의 방을 고르게 했는데 자꾸만 틀리네요.

고수님들의 도움 부탁드립니다!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution13424 {
    static final int INF = 50_000;
    static List<Node>[] map;
    static int[] distance;
    static boolean[] visited;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            map = new ArrayList[n + 1];
            distance = new int[n + 1];
            visited = new boolean[n + 1];
            for (int i = 1; i < map.length; i++) {
                map[i] = new ArrayList<>();
            }

            while (m-- > 0) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());

                map[a].add(new Node(b, c));
                map[b].add(new Node(a, c));
            }
            int k = Integer.parseInt(br.readLine());
            int[] position = new int[k];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < position.length; i++) {
                position[i] = Integer.parseInt(st.nextToken());
            }
            int answer = dijkstra(position);
            bw.write(answer + "\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }

    static int dijkstra(int[] position) {
        int[] answerArr = new int[distance.length];
        PriorityQueue<Node> pq = new PriorityQueue<>();

        for (int i = 0; i < position.length; i++) {
            int start = position[i];
            for (int j = 1; j < distance.length; j++) {
                distance[j] = INF;
                visited[j] = false;
            }
            distance[start] = 0;
            pq.offer(new Node(start, 0));
            while (!pq.isEmpty()) {
                Node current = pq.poll();
                visited[current.node] = true;
                List<Node> adjList = map[current.node];
                for (int j = 0, size = adjList.size(); j < size; j++) {
                    Node nextNode = adjList.get(j);
                    if (!visited[nextNode.node] && distance[nextNode.node] > distance[current.node] + nextNode.cost) {
                        distance[nextNode.node] = distance[current.node] + nextNode.cost;
                    }
                }
            }
            for (int j = 1; j < answerArr.length; j++) {
                answerArr[j] += distance[j];
            }
        }

        int answer = 1;
        int roomDistance = answerArr[1];
        for (int i = 2; i < answerArr.length; i++) {
            if (roomDistance > answerArr[i]) {
                answer = i;
                roomDistance = answerArr[i];
            } else if (roomDistance == answerArr[i] && answer > i) {
                answer = i;
            }
        }
        return answer;
    }
}

class Node implements Comparable<Node> {
    int node;
    int cost;

    public Node(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node o) {
        return this.cost - o.cost;
    }

}

jeongyong95 3년 전 0

76번 줄 다음에 pq.offer 해서 노드와 거리를 넣어줘야 했네요!

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

문제

문제

출처

ICPC

다익스트라를 반복해서 답을 구하는데 어디가 틀렸는지 모르겠습니다.

jeongyong95 3년 전 0

jeongyong95 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말