[JAVA] 백준 6054 - Relay Race

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

 

소들의 릴레이 경주에 대한 정보가 주어졌을 때, 마지막 소가 들어온 시간이 몇 초인지 구하는 문제이다.

 

출발 소 , 도착 소, 가중치 정보를 저장하고 다익스트라로 1번 소에서 각각의 소까지의 거리를 구한다음 마지막에 각 소별로 뛰는 거리를 더해준 후 그 최댓값을 구했다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cowCount = Integer.parseInt(br.readLine());
        int[] arr = new int[cowCount+1];
        int[] costs = new int[cowCount+1];
        Arrays.fill(arr, Integer.MAX_VALUE);
        arr[0] = 0;
        arr[1] = 0;
        List<Vertex>[] edges = new ArrayList[cowCount+1];

        for(int i = 0; i<cowCount; i++){
          int[] temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
          int cow = i+1;
          int cost = temp[0];
          costs[cow] = cost;
          edges[cow] = new ArrayList<>();
          int edgeCount = temp[1];
          for(int j = 2; j<=(2+edgeCount-1); j++ ){
            Vertex v = new Vertex(temp[j], cost);
            edges[cow].add(v);
          }
        }
        boolean[] visited = new boolean[cowCount+1];
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x->x[1]));
        pq.offer(new int[]{1,0});
        while(!pq.isEmpty()){
          int[] tar = pq.poll();
          int value = tar[0];
          int weight = tar[1]; 
          if(visited[value]) continue;
          visited[value] = true;
          List<Vertex> vList = edges[value];
          for(int i = 0; i<vList.size(); i++ ){
            Vertex v = vList.get(i);
            if(weight + v.weight <= arr[v.to]){
                arr[v.to] = weight+ v.weight;
                pq.offer(new int[]{v.to, arr[v.to]});
            }
          }
        }
        for(int i = 0; i<=cowCount; i++){
            arr[i] = arr[i] + costs[i];
        }

        System.out.println(Arrays.stream(arr).max().getAsInt());
    }
}

class Vertex{
    int to;
    int weight;
    Vertex(int to, int weight){
        this.to = to;
        this.weight = weight;
    }
}