두 노드를 지나는 최소 비용

일단 가중치들에서 음수가 없으로 다익스트라 알고리즘을 활용한다.

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Practice1 {

    static ArrayList<ArrayList<Node>> graph;
    static final int INF = 1111111;

    static class Node{
        int to;
        int weight;

        public Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static int solution(int[][] data, int v, int via1, int via2, int start, int n) {
        int case1 = 0;
        int case2 = 0;

        // 그래프 구성
        graph = new ArrayList<>();
        for (int i = 0; i < v + 1; i++) {
            graph.add(new ArrayList<>());
        }

        //그래프에 간선들 정보 추가
        for (int i = 0; i < data.length; i++) {
            graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
        }

        // Case1: start -> via1 -> via2 - > n
        case1 += dijkstra(v, start, via1);
        case1 += dijkstra(v, via1, via2);
        case1 += dijkstra(v, via2, n);

        // Case2: start -> via2 -> via1 -> n
        case2 += dijkstra(v, start, via2);
        case2 += dijkstra(v, via2, via1);
        case2 += dijkstra(v, via1, n);

        // 해당 경로가 없는 경우는 -1
        // 있는 경우는 작은 값 반환
        if(case1 >= INF && case2 >= INF) {
            return -1;
        } else {
            return Math.min(case1, case2);
        }
    }

    public static int dijkstra(int v, int start, int end) {
        //우선순위 큐 가중치가 짧은것부터 들어옴
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>((x, y) -> x.weight - y.weight);
        priorityQueue.offer(new Node(start,0));

        //1~n까지 도착시 최소 가중치를 담고있음
        int[] dist = new int[v+1];
        boolean[] visited = new boolean[v+1];
        for(int i = 0 ; i < v+1; i++){// 초기화
            dist[i] = INF;
        }

        dist[start] = 0;

        while (!priorityQueue.isEmpty()){
            Node curNode = priorityQueue.poll(); // 처음에는 to : 1 weight = 0

            if(visited[curNode.to]){//방문한 노드는 넘어가기 위함
                continue;
            }

            visited[curNode.to] = true;

            for (int i = 0; i < graph.get(curNode.to).size(); i++) {
                Node adjNode = graph.get(curNode.to).get(i); // adj의 노드는 처음 기준으로 1번노드와 관계가 있는 2,3,4,번 노드의 정보가 들어있음 

                // 방문 배열 체크 추가
                //기존 배열의 값보다 거쳐가는 값이 작다면 바꿔줌
                if (!visited[adjNode.to] && dist[adjNode.to] > curNode.weight + adjNode.weight) {
                    dist[adjNode.to] = curNode.weight + adjNode.weight;
                    priorityQueue.offer(new Node(adjNode.to, dist[adjNode.to]));
                }
            }
        }

        return dist[end];
    }

    public static void main(String[] args) {
        // Test code
        int[][] data = {{1, 2, 3}, {1, 3, 5}, {1, 4, 4}, {2, 3, 3}, {2, 4, 5}, {3, 4, 1}};
        int v = 4;
        int via1 = 2;
        int via2 = 3;
        int start = 1;
        int n = 4;

        System.out.println(solution(data, v, via1, via2, start, n));
    }
}