[JAVA/백준] 10282번: 해킹

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.util.*;
import java.io.*;
/**
 * @author HEESOO
 *
 */
class Main {	
	static int[] dist;
	static ArrayList<ArrayList<Node>> list;
	static int cnt;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int tc=Integer.parseInt(br.readLine());
		
		while(tc-->0) {
			st=new StringTokenizer(br.readLine());
			int n=Integer.parseInt(st.nextToken()); // 총 컴퓨터 수
			int d=Integer.parseInt(st.nextToken()); // 감염 정보 수
			int c=Integer.parseInt(st.nextToken()); // 시작 컴퓨터
			
			dist=new int[n+1]; // 0번은 사용 안함
			Arrays.fill(dist, Integer.MAX_VALUE); // INF로 초기화
			list=new ArrayList<>();
			for(int i=0;i<=n;i++) 
				list.add(new ArrayList<>());
			cnt=1; // 시작 컴퓨터는 이미 감염되었으므로
			
			PriorityQueue<Node> pq=new PriorityQueue<>();
			pq.offer(new Node(c, 0));
			dist[c]=0; // 시작 노드이므로 0으로 초기화
			
			for(int i=0;i<d;i++) {
				st=new StringTokenizer(br.readLine());
				int a=Integer.parseInt(st.nextToken());
				int b=Integer.parseInt(st.nextToken());
				int s=Integer.parseInt(st.nextToken());				
				list.get(b).add(new Node(a, s)); // b->a로 감염됨
			}

			solve(pq);
			// dist에서 INF를 제외한 새 배열 생성
			int[] result=Arrays.stream(dist).filter(k->k!=Integer.MAX_VALUE).toArray();
			Arrays.sort(result);
			System.out.println(cnt+" "+result[result.length-1]);
		}
		
	}
	
	public static void solve(PriorityQueue<Node> pq) {
		while(!pq.isEmpty()) {
			Node node=pq.poll();
			// 내 weight가 계산된 dist보다 크다면 갱신할 필요 없음
			if(node.weight>dist[node.idx]) continue;
			
			for(Node n:list.get(node.idx)) { // node에서 갈 수 있는 n
				// n으로 가는 것 중 node에서 n으로 가는 경우가 더 최단이라면
				if(dist[n.idx]>dist[node.idx]+n.weight) {
					if(dist[n.idx]==Integer.MAX_VALUE) cnt++; // n 방문이 처음이라면
					dist[n.idx]=dist[node.idx]+n.weight;
					pq.offer(new Node(n.idx, dist[n.idx]));
				}
				
			}
		}
	}
	
}
class Node implements Comparable<Node>{
	int idx;
	int weight;
	
	public Node(int i, int w) {
		this.idx=i;
		this.weight=w;
	}
	
	@Override
	public int compareTo(Node n) { // weight 기준 오름차순 정렬
		return this.weight-n.weight;
	}
}