이번에 풀어본 문제는
백준 1238번 파티 입니다.

📕 문제 링크

❗️코드

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

class Town
{
    int next,weight;

    public Town(int next, int weight) {
        this.next = next;
        this.weight = weight;
    }
}
public class Main {
    static int N,M,X;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        List<List<Town>> list,reverseList;
        list = new ArrayList<>();
        reverseList = new ArrayList<>();

        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
            reverseList.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            list.get(start).add(new Town(end,weight));
            reverseList.get(end).add(new Town(start,weight));
        }

        int [] go = search(list);
        int [] back = search(reverseList);

        int answer = Integer.MIN_VALUE;
        for (int i = 1; i <= N; i++) {
            answer = Math.max(answer, go[i] + back[i]);
        }

        System.out.print(answer);
    }
    //다익
    static int [] search(List<List<Town>> list) {
        Queue<Town> pq = new PriorityQueue<>(new Comparator<Town>() {
            @Override
            public int compare(Town t1, Town t2) {
                return t1.weight - t2.weight;
            }
        });
        int [] arr = new int[N + 1];
        Arrays.fill(arr, Integer.MAX_VALUE);
        arr[X] = 0;
        boolean [] isVisited = new boolean[N + 1];
        pq.add(new Town(X,0));
        while (!pq.isEmpty()) {
            Town cur = pq.poll();
            if(!isVisited[cur.next]) {
                isVisited[cur.next] = true;

                for (Town town : list.get(cur.next)) {
                    if(!isVisited[town.next] && (arr[town.next] > arr[cur.next] + town.weight)) {
                        arr[town.next] = arr[cur.next] + town.weight;
                        pq.add(new Town(town.next,arr[town.next]));
                    }
                }
            }
        }
        return arr;
    }
}

📝 풀이

각 정점에서 X 정점을 찍고 돌아올 수 있는 최단 경로 중 가장 큰 값을 구하는 문제입니다.
정점에서 X까지의 최단거리 + X에서 각 정점까지의 최단거리를 구하면 됩니다.
다익스트라 알고리즘을 활용해서 입력값 그대로 X부터 각 정점까지의 최소 거리를 구하고,
입력값을 반대로 뒤집어서 한번 더 수행해주면 두 값 모두 구해낼 수 있습니다.

📜 후기

입력값의 범위가 커서 다익스트라 알고리즘을 선택하긴 했지만, 단방향 연결의 순서를 뒤집는 발상은 하지 못해서 다른 풀이를 보고 해답을 찾았습니다. 놀랍네요;