https://www.acmicpc.net/problem/1238

파티

풀이

일반적인 다익스트라 알고리즘은 출발지가 고정되어 있을 때 해당 출발지로부터 모든 노드에 도착하는 비용을 구한다.

하지만 이번 문제는 도착지가 x로 고정되어 있고 각 출발지에서 도착지 x로 가는 경로의 비용을 구해야한다.

그래서 모든 출발지에 대해 다익스트라 알고리즘을 이용해 거리를 구했고 그 중 x까지의 값만 가져온다.

또한 출발지에서 출발한 사람은 x를 갔다가 다시 원래 출발지로 돌아가기 때문에 x에서 출발하여 여러 노드로 도착하는 경로의 비용을 다익스트라 알고리즘을 이용해 구했다.

결국 출발지에서 출발하여 x를 갔다가 다시 돌아오는 비용은 위에서 구한 두 값의 합이고 이 중 최대인 값을 찾으면 된다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static final int INF = 100000001;
    static int n, m;
    static int x;
    static ArrayList<Pair>[] graph;
    static PriorityQueue<Pair> queue;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] first = br.readLine().split(" ");
        n = Integer.parseInt(first[0]);
        m = Integer.parseInt(first[1]);
        x = Integer.parseInt(first[2]);
        graph = new ArrayList[n + 1];
        queue = new PriorityQueue<>();

        for (int i = 0; i <= n; i++)
            graph[i] = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < line.length; j++) {
                int x = Integer.parseInt(line[0]);
                int y = Integer.parseInt(line[1]);
                int w = Integer.parseInt(line[2]);
                graph[x].add(new Pair(y, w));
            }
        }
        ArrayList<int[]> toDest = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            int[] temp = dijkstra(i);
            toDest.add(temp);
        }

        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0;i< toDest.size();i++) {
            int a = toDest.get(i)[x] + toDest.get(x-1)[i + 1];
            ans.add(a);
        }

        System.out.println(Collections.max(ans));

        bw.close();
        br.close();
    }

    private static int[] dijkstra(int start) {
        int[] dist = new int[n + 1];
        boolean[] visited = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            if (i == start)
                dist[i] = 0;
            else
                dist[i] = Integer.MAX_VALUE;
        }

        queue.offer(new Pair(start, 0));
        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            int y = p.y;
            if (visited[y])
                continue;
            else
                visited[y] = true;

            for (Pair next : graph[y]) {
                if (dist[next.y] >= dist[y] + next.w) {
                    dist[next.y] = dist[y] + next.w;
                    queue.offer(new Pair(next.y, dist[next.y]));
                }
            }
        }
        return dist;
    }
}

class Pair implements Comparable<Pair> {
    public int y;
    public int w;

    public Pair(int y, int w) {
        this.y = y;
        this.w = w;
    }

    @Override
    public int compareTo(Pair o) {
        return Integer.compare(this.w, o.w);
    }
}