글 읽기 - 자기 자신으로 가는 길도 있을수 있나요?

bethejustice 2년 전 0

1 - a1 - a2 - N 으로 가는 길을 다익스트라 세번으로 구하고

1 - a2 - a1 - N 으로 가는 길을 다익스트라로 세번으로 구해서

2번모두 한번이라도 INF가 나오면 -1을 출력하게 하였고

그렇지 않으면 둘중에서 더 짧은 길을 선택하라고 하였습니다.

1% 통과 못하는데... 뭘 잘못 생각한걸까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_1504 {

    static final int INF = 800000;
    static List<Edge>[] map;
    static int node;
    static int edge;


    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        node = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());

        map = new ArrayList[node+1];

        for(int i = 1; i <= node ; i++){
            map[i] = new ArrayList<>();
        }

        for(int i = 1; i <= edge ; i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            map[from].add(new Edge(to, value));
            map[to].add(new Edge(from, value));
        }

        st = new StringTokenizer(br.readLine());

        int mid1 = Integer.parseInt(st.nextToken());
        int mid2 = Integer.parseInt(st.nextToken());

        int result1 = dijk(1, mid1) + dijk(mid1, mid2) + dijk(mid2, node);
        int result2 = dijk(1, mid2) + dijk(mid2, mid1) + dijk(mid1, node);

        if(result1 >= INF && result2 >= INF){
            System.out.println(-1);
            return;
        }

        if (result1 > result2) {
            System.out.println(result2);
        } else {
            System.out.println(result1);
        }


    }

    static int dijk(int start, int finish){

        if(start == finish) return 0;

        int[] dist = new int[node+1];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        Queue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(start, 0));

        while(!pq.isEmpty()){
            Edge current = pq.poll();

            for(int i = 0; i < map[current.to].size(); i++){
                Edge next = map[current.to].get(i);

                if(dist[next.to] > dist[current.to] + next.value){

                    dist[next.to] = dist[current.to] + next.value;
                    if(next.to == finish){
                        return dist[next.to];
                    }
                    pq.add(new Edge(next.to, dist[next.to]));
                }
            }
        } //while

        return INF;
    }

    static class Edge implements Comparable<Edge>{
        int to;
        int value;

        public Edge(int to, int value) {
            this.to = to;
            this.value = value;
        }

        @Override
        public int compareTo(Edge o) {
            return this.value>o.value ? 1:-1;
        }
    }
}

djm03178 2년 전 1

어떤 종류의 탐색이든 next를 보고 처리하는 것보다는 current에서 처리하는 게 안전합니다. 과연 80번째 줄이 나올 때 확인한 거리가 최적이라는 보장이 있을까요?

bethejustice 2년 전 0

@ djm03178

간단하지만 중요한원리네요.. 이렇게 쉽게 풀리다니 감사합니다..

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

문제

문제

출처

ICPC

자기 자신으로 가는 길도 있을수 있나요?

bethejustice 2년 전 0

djm03178 2년 전 1

bethejustice 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말