백준 12834 자바 - 주간 미팅 (BOJ 12834 JAVA)

문제 : boj12834

 

 

  문제의 입력 최대값 제한에 자비심이 넘치는 문제이다. 사실상 Floyd-Warshall만 딱 못쓰게 제한 걸고(V<=1000), 다익스트라로는 뭐 대충 뭔짓을 하던 통과되게 자비로웠다.

 

1.

  각 N개의 노드에서 A와 B 두 곳으로 가는 최단거리를 모두 구하면 된다. 이 때 Floyd-Warshall로 하면 제일 편하겠지만, V<=1000에 따라 O(V^3) 정도가 걸릴 플로이드 와샬로는 통과가 불가하다. 그렇다고 BFS로는 거리가 서로 다르므로 불가능하고, 딱히 음수값도 없으니 그냥 다익스트라를 쓰면 되겠다는 점은 바로 파악할 수 있다.

그럼 O(NElogV) 정도가 걸리고, 이렇게 해도 1000만번 수준이므로 통과하는데 문제가 없다.

 

2.  

  여기서 N을 빼버리고 O(ElogV) 두번으로도 가능하다. 다익스트라는 일반적으로 '한 점에서 모든 점으로의 최단거리'로 이해하고 있지만, 무방향 그래프라면 그 반대인 '모든 점에서 한 점으로의 최단거리'도 된다(방향 그래프라도 모든 간선을 역방향으로 바꾸면 가능하다.).

 

  따라서 A에서 모든 곳으로의 최단거리와 B에서 모든 곳으로의 최단거리를 구한 후, N개의 지점에 대해 단순 덧셈으로 답을 구할 수 있다. 이게 '1'보다 당연히 효율적이지만, '1'로도 통과되게 해둔걸 보니 출제자의 자비로움이 느껴졌다.

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

class Edge {
    int to, dist;
    public Edge(int to, int dist) {
        this.to = to;
        this.dist = dist;
    }
}

class Node implements Comparable<Node> {
    int num, distFromStart;
    public Node(int num, int distFromStart) {
        this.num = num;
        this.distFromStart = distFromStart;
    }

    @Override
    public int compareTo(Node o) {
        return this.distFromStart - o.distFromStart;
    }
}

public class Main extends FastInput {
    private static final int INFINITY = 10000*100+1;

    private int[] findAllShortestDistFromStart(int v, int start, ArrayList<Edge>[] edges) {
        int[] res = new int[v+1];
        Arrays.fill(res, INFINITY);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        res[start] = 0;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if (res[cur.num] < cur.distFromStart) continue;

            for (Edge next : edges[cur.num]) {
                if (res[next.to] <= cur.distFromStart + next.dist) continue;
                res[next.to] = cur.distFromStart + next.dist;
                pq.add(new Node(next.to, res[next.to]));
            }
        }

        return res;
    }

    private void solution() throws Exception {
        int n = nextInt();
        int v = nextInt();
        int e = nextInt();

        int goal1 = nextInt();
        int goal2 = nextInt();

        int[] member = new int[n+1];
        for (int i = 1; i <= n; i++) member[i] = nextInt();

        ArrayList<Edge>[] edges = new ArrayList[v+1];
        for (int i = 1; i <= v; i++) edges[i] = new ArrayList<>();
        while(e-->0) {
            int a = nextInt();
            int b = nextInt();
            int l = nextInt();
            edges[a].add(new Edge(b, l));
            edges[b].add(new Edge(a, l));
        }

        int[] res1 = findAllShortestDistFromStart(v, goal1, edges);
        int[] res2 = findAllShortestDistFromStart(v, goal2, edges);

        int sum = 0;
        for (int i = 1; i <= n; i++) {
            int distToGoal1 = res1[member[i]] == INFINITY ? -1 : res1[member[i]];
            int distToGoal2 = res2[member[i]] == INFINITY ? -1 : res2[member[i]];
            sum += distToGoal1 + distToGoal2;
        }
        System.out.println(sum);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}