[JAVA] 백준 1719 - 택배

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

N개의 정점 중 특정 정점 A에서 B로 갈 때 가장 첫번째로 지나야하는 정점을 저장하는 배열을 반환하는 문제이다.

N번 다익스트라를 돌려서 해결했는데, 그 와중에 Node를 재사용하는 바람에 몇번 틀렸다 ㅠㅠ

 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        List<List<Road>> list = new ArrayList<>();
        for (int i = 0; i <= info[0]; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < info[1]; i++) {
            int[] vertex = getArray(br.readLine());
            list.get(vertex[0]).add(new Road(vertex[1],vertex[2]));
            list.get(vertex[1]).add(new Road(vertex[0],vertex[2]));
        }
        PriorityQueue<Company> pq = new PriorityQueue<>();
        int[][] ans = new int[info[0]+1][info[0]+1];

        for (int i = 1; i <= info[0]; i++) {
            List<Company> companyList = new ArrayList<>();
            int[] dist = new int[info[0]+1];
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[i] = 0;
            for (int j = 0; j <= info[0]; j++) {
                companyList.add(new Company(j,j));
            }
            Company start = companyList.get(i);
            start.cost = 0;
            pq.offer(start);
            while(!pq.isEmpty()){
                Company target = pq.poll();
                int value = target.value;
                int parent = target.parent;
                int cost = target.cost;
                if(cost>dist[value]) continue;
                ans[i][value] = parent;
                List<Road> map = list.get(value);
                for(Road r : map){
                    int c = r.cost;
                    int cCost = dist[r.to];
                    if(cCost>cost+c){
                        dist[r.to] =  cost + c;
                        if(parent==i){
                            pq.offer(new Company(r.to,r.to,dist[r.to]));
                        }else{
                            pq.offer(new Company(r.to, parent, dist[r.to]));
                        }
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < ans.length ; i++) {
            for (int j = 1; j < ans[0].length; j++) {
                if(i==j){
                    sb.append("- ");
                }else{
                    sb.append(ans[i][j]+ " ");
                }
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class Company implements Comparable<Company> {
    int value;
    int parent;
    int cost = Integer.MAX_VALUE;

    Company(int v, int p){
        this.value = v;
        this.parent = p;
    }

    Company(int v, int p, int cost){
        this.value = v;
        this.parent = p;
        this.cost = cost;
    }

    @Override
    public int compareTo(Company o) {
        return this.cost-o.cost;
    }
}

class Road{
    int to;
    int cost;
    Road(int t, int c){
        this.to = t;
        this.cost = c;
    }
}