https://school.programmers.co.kr/learn/courses/30/lessons/72413

X지점에서 환승을 할 경우 총 거리는 dist(s->x) + dist(x->b) + dist(x->a) = dist(s->x) + dist(b->x) + dist(a->x) 이다. (방향에 따라 거리 변화가 없음)

다익스트라 알고리즘으로 시작점 s, A의 도착점 a, B의 도착점 b에서 모든 지점까지의 최단거리를 구한다.
그 후 answer를 Max값으로 초기화 시킨후 1 ~ n 까지 for문을 돌리며 각 지점이 환승점이 될 경우 거리를 구한다.

이때 s 지점이 환승점이 될 경우 환승 하지 않을 경우 즉 거리(s->a) + 거리(s->b)와 동일하게 된다.

제출 코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;

class Solution {
    static final int INF = 200 * 100000 + 1;
    static LinkedList<Edge>[] map;
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        map = new LinkedList[n + 1];
        for (int i = 1; i <= n; i++)
            map[i] = new LinkedList<>();

        for (int i = 0; i < fares.length; i++) {
            int[] fare = fares[i];
            map[fare[0]].add(new Edge(fare[1], fare[2]));
            map[fare[1]].add(new Edge(fare[0], fare[2]));
        }
        
        int[] distA = new int[n + 1];
        int[] distB = new int[n + 1];
        int[] distS = new int[n + 1];

        Arrays.fill(distA, INF);
        Arrays.fill(distB, INF);
        Arrays.fill(distS, INF);

        distA = Dijkstra(distA, a);
        distB = Dijkstra(distB, b);
        distS = Dijkstra(distS, s);

        int answer = distS[a] + distS[b];
        for (int i = 1; i <= n; i++) {
            answer = Math.min(answer, distS[i] + distA[i] + distB[i]);
        }
        return answer;
    }
    static public int[] Dijkstra(int[] dist, int str) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();

        pq.offer(new Edge(str, 0));
        dist[str] = 0;

        while (!pq.isEmpty()) {
            Edge now = pq.poll();
            int n_num = now.num;
            int n_dist = now.dist;

            if (n_dist > dist[n_num])
                continue;

            for (Edge e : map[now.num]) {
                int t_dist = dist[n_num] + e.dist;
                if (t_dist < dist[e.num]) {
                    dist[e.num] = t_dist;
                    pq.offer(new Edge(e.num, t_dist));
                }
            }
        }
        return dist;
    }
    
    static class Edge implements Comparable<Edge>{
        public int num;
        public int dist;
        public Edge(int num, int dist) {
            this.num = num;
            this.dist = dist;
        }
        @Override
        public int compareTo(Edge e) {
            return Integer.compare(this.dist, e.dist);
        }
    }
}

참고 링크 : https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://wellbell.tistory.com/101