[백준]1504: 특정한 최단 경로 - JAVA

[백준]1504: 특정한 최단 경로

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

풀이

1에서 시작해서 V1과 V2를 포함하여 N까지 가는 최단 경로 값을 찾는 문제이다.

 

간단하게 생각하면된다. 다음과 같은 두 경로를 구한 후 둘 중에 더 작은 경로를 출력하면 된다.

1. 최단거리(1 ~ V1) + 최단거리(V1 ~ V2) + 최단거리(V2 ~ N)

2. 최단거리(1 ~ V2) + 최단거리(V2 ~ V1) + 최단거리(V1 ~ N)

한 정점에서 부터 모든 정점 까지의 경로를 구하는 다익스트라를 사용해서 각각의 최단거리를 구해주었다.

 

dist배열을 최대값으로 초기화 시켜주어서 만약 한 정점에서 다른 정점으로의 경로가 없다면 최대값이 반환되도록 하였다. 그래서 1, 2번 경로 모두가 최대값보다 크거나 같다면 1,2번 경로 둘다 유효하지 않은 경로이기 때문에 -1을 반환하도록 하였다.

 

코드

import java.util.*;
 
public class Main {    
    
    static ArrayList<Node>[] list;
    static int n;
    static int max = 200000000;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        int e = scan.nextInt();
        
        list = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < e; i++) {
            int f = scan.nextInt();
            int t = scan.nextInt();
            int cost = scan.nextInt();
            list[f].add(new Node(t, cost));
            list[t].add(new Node(f, cost));
        }
        
        int n1 = scan.nextInt();
        int n2 = scan.nextInt();
        
        int len1 = dijkstra(1, n1) + dijkstra(n1, n2) + dijkstra(n2, n);
        int len2 = dijkstra(1, n2) + dijkstra(n2, n1) + dijkstra(n1, n);
        
        int min = 0;
        if(len1 >= max && len2 >= max) min = -1;
        else min = Math.min(len1, len2);
        System.out.println(min);
    }
    
    public static int dijkstra(int start, int end) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(start, 0));
        
        int[] dist = new int[n + 1];
        boolean[] visited = new boolean[n + 1];
        Arrays.fill(dist, max);
        dist[start] = 0;
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            
            if(visited[current.x] == false) visited[current.x] = true;
            else continue;
            
            for(int i = 0; i < list[current.x].size(); i++) {
                Node next = list[current.x].get(i);
                if(visited[next.x] == false && dist[next.x] > dist[current.x] + next.cost) {
                    dist[next.x] = dist[current.x] + next.cost;
                    q.offer(new Node(next.x, dist[next.x]));
                }
            }
        }
        
        return dist[end];
    }
    
    public static class Node implements Comparable<Node> {
        int x;
        int cost;
        
        public Node(int x, int cost) {
            this.x = x;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node n) {
            return this.cost - n.cost;
        }
    }
}