1238 파티 [JAVA]

문제 분석

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

각 지점에서 X로 또, X에서 각 지점으로 최소의 비용으로 움직일 때

전체 지점 중 왕복 비용의 최댓값을 구하는 문제다.

 

다익스트라를 순방향, 역방향으로 2번 사용하여 풀 수 있다.

 

max cost를 처음에 너무 낮게 잡아 계속 틀렸었으나..

각 마을간 도로는 1개고 순환 도로는 없으니 max cost는 마을의 갯수 * 도로의 최대 비용이다. 즉, 1000*100이다.

코드

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int x = sc.nextInt();
        Town[] towns = new Town[n+1];
        for (int i = 1; i <= n; i++) {
            towns[i] = new Town(i);
        }

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int cost = sc.nextInt();
            towns[a].roads.add(new Road(b,cost));
            towns[b].reverseRoads.add(new Road(a,cost));
        }
        //reverse way
        int[] toX = new int[n+1];

        //normal way
        int[] fromX = new int[n+1];

        for (int i = 0; i < n + 1; i++) {
            toX[i]=fromX[i] = 1000*100+1;
        }
        toX[x]=fromX[x]=0;

        //find min way from X
        PriorityQueue<Road> nextRoads = new PriorityQueue<>(Comparator.comparingInt(o -> o.cost));
        nextRoads.add(new Road(x,0));

        while (!nextRoads.isEmpty()){
            Road poll = nextRoads.poll();

            if(poll.cost > fromX[poll.idx])
                continue;

            for (Road road : towns[poll.idx].roads) {
                if(fromX[road.idx] > fromX[poll.idx] + road.cost){
                    fromX[road.idx] = fromX[poll.idx] + road.cost;
                    nextRoads.add(new Road(road.idx, fromX[road.idx]));
                }
            }
        }

        //find min way to X
        nextRoads.add(new Road(x,0));

        while (!nextRoads.isEmpty()){
            Road poll = nextRoads.poll();

            for (Road road : towns[poll.idx].reverseRoads) {
                if(toX[road.idx] > toX[poll.idx] + road.cost){
                    toX[road.idx] = toX[poll.idx] + road.cost;
                    nextRoads.add(new Road(road.idx, toX[road.idx]));
                }
            }
        }

        //find max cost sum
        int maxCost = 0;
        for (int i = 1; i <= n; i++) {
            maxCost = Math.max(fromX[i]+toX[i], maxCost);
        }
        System.out.println(maxCost);
    }

    static class Town{
        int idx;
        Set<Road> roads;
        Set<Road> reverseRoads;
        public Town(int idx){
            this.idx= idx;
            roads = new HashSet<>();
            reverseRoads = new HashSet<>();
        }
    }

    static class Road{
        int idx,cost;
        public Road(int idx, int cost){
            this.idx=idx;
            this.cost=cost;
        }
    }


// 2 - 3 - 4 = 9
    // 2 - 1 - 4 = 1+7 = 8
    // 2 - 1 - 3 -4 = 1+2+4= 7
}