[JAVA] 1719 택배 (다익스트라)

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

1719번: 택배

 

모든 정점에서 다익스트라를 실행해서 첫번째로 탐색되는 정점을 저장하면서 업데이트 하였습니다.

출력하는 방식이 헷갈려서 조금 오래걸린 문제ㅜ.ㅜ

 

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

public class Main {

    public static class vertex implements Comparable<vertex> {
        int v;  int t;

        public vertex(int v, int t) {
            this.v = v;
            this.t = t;
        }

        @Override
        public int compareTo(vertex o) {
            return this.t - o.t;
        }
    }

    public static class edge implements Comparable<edge> {
        int v;  int t;

        public edge(int v, int t) {
            this.v = v;
            this.t = t;
        }

        @Override
        public int compareTo(edge o) {
            return this.v - o.v;
        }
    }

    static void dijkstra(int start, int n, int order, List<Integer> sortedVertices, List<edge>[] edges, int[][] res) {
        boolean[] visited = new boolean[201];
        int[] distance = new int[201];
        int[] firstVisitVertex = new int[201];
        PriorityQueue<vertex> pq = new PriorityQueue<>();

        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;
        firstVisitVertex[start] = 0;
        pq.add(new vertex(start, 0));

        while (!pq.isEmpty()) {
            vertex cur = pq.poll();

            if (visited[cur.v])   continue;
            visited[cur.v] = true;

            for (int i=0; i<edges[cur.v].size(); i++) {
                int next = edges[cur.v].get(i).v;
                int t = edges[cur.v].get(i).t;
                if (!visited[next] && distance[cur.v] + t < distance[next]) {
                    if (cur.v == start) firstVisitVertex[next] = next;
                    else    firstVisitVertex[next] = firstVisitVertex[cur.v];
                    distance[next] = distance[cur.v] + t;
                    pq.add(new vertex(next, distance[next]));
                }
            }
        }

        Collections.sort(edges[start]);
        for (int i=0; i<n; i++) {
            int v = sortedVertices.get(i);
            res[order][i] = firstVisitVertex[v];
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(token.nextToken());
        int m = Integer.parseInt(token.nextToken());
        Set<Integer> vertices = new HashSet<>();
        List<edge>[] edges = new ArrayList[201];

        int[][] res = new int[201][201];

        for (int i=0; i<m; i++) {
            token = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(token.nextToken());
            int v = Integer.parseInt(token.nextToken());
            int t = Integer.parseInt(token.nextToken());

            vertices.add(u);    vertices.add(v);

            if (edges[u] == null) edges[u] = new ArrayList<>();
            if (edges[v] == null) edges[v] = new ArrayList<>();

            edges[u].add(new edge(v, t));
            edges[v].add(new edge(u, t));
        }

        List<Integer> sortedVertices = new ArrayList<>();
        sortedVertices.addAll(vertices);
        Collections.sort(sortedVertices);

        for (int i=0; i<n; i++) {
            dijkstra(sortedVertices.get(i), n, i, sortedVertices, edges, res);
        }

        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (res[i][j] == 0) System.out.print("- ");
                else System.out.print(res[i][j] + " ");
            }
            System.out.println();
        }
    }
}