[백준 10282] 해킹(Java)

1. 문제

www.acmicpc.net/problem/10282

10282번: 해킹

2. 풀이

• 다익스트라 응용

3. 코드

import java.util.*;
import java.io.*;
 
public class Main {
 
	public static class Node implements Comparable<Node> {
        int to, weight;
 
        public Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
 
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }
	
	static final int INF =987654321;
	static int v,e,c;
	static int[]visited;
	static ArrayList<Node>[]list;
 
    public static void main(String[] args) throws IOException {
    	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	 StringTokenizer st;
    	 int tc = Integer.parseInt(br.readLine());
    	 
         for (int i = 0; i < tc; i++) {
             st = new StringTokenizer(br.readLine());
  
             v = Integer.parseInt(st.nextToken());
             e = Integer.parseInt(st.nextToken());
             int start = Integer.parseInt(st.nextToken());
  
             list = new ArrayList[v + 1];
             visited = new int[v + 1];
             Arrays.fill(visited, INF);
  
             c = 1; 
  
             for (int j = 1; j <= v; j++)
            	 list[j] = new ArrayList<>();
  
             for (int j = 0; j < e; j++) {
                 st = new StringTokenizer(br.readLine());
  
                 int from = Integer.parseInt(st.nextToken());
                 int to = Integer.parseInt(st.nextToken());
                 int cost = Integer.parseInt(st.nextToken());
  
                 list[to].add(new Node(from, cost)); 
             }
  
             bfs(start);
                                            
             int[] result = Arrays.stream(visited).filter(k -> k != INF).toArray(); 
             Arrays.sort(result);                                                
             System.out.println(c+" "+result[result.length - 1]);
 
         }
  
      
    }
    public static void bfs(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        
        visited[start] = 0;
        pq.offer(new Node(start, visited[start]));
 
        while (!pq.isEmpty()) {
        	Node from = pq.poll();
 
            if (from.weight > visited[from.to])
                continue;
 
            for (Node to : list[from.to]) {
                if (visited[to.to] > visited[from.to] + to.weight) {
                    if(visited[to.to] == INF) 
                        c++;           
                    visited[to.to] = visited[from.to] + to.weight;
                    pq.offer(new Node(to.to, visited[to.to]));
                }
            }
        }
    }
 
    
 
    
}

반응형