내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int T, n, d, c;
static ArrayList<ArrayList<int[]>> list;
static boolean[] check;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
for (int tc = 0; tc < T; tc++) {
int count = 0;
int gap = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
check = new boolean[n + 1];
list = new ArrayList<>();
for (int i = 0; i <= n; i++) {
list.add(new ArrayList<>());
}
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 int[]{a, s});
}
Queue<Node> pq = new PriorityQueue<>();
pq.add(new Node(c, 0));
while (!pq.isEmpty()) {
Node node = pq.poll();
if (check[node.com])
continue;
check[node.com] = true;
count++;
gap = Math.max(node.time, gap);
for (int i = 0; i < list.get(node.com).size(); i++) {
int[] tmp = list.get(node.com).get(i);
if (!check[tmp[0]]) {
pq.add(new Node(tmp[0], node.time + tmp[1]));
}
}
}
System.out.println(count + " " + gap);
}
}
static class Node implements Comparable<Node> {
int com, time;
public Node(int com, int time) {
this.com = com;
this.time = time;
}
@Override
public int compareTo(Node o) {
return this.time - o.time;
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
백양로 브레이크 - 11562번 (0) | 2022.01.19 |
---|---|
회문 - 17609번 (0) | 2021.12.30 |
소수 화폐 (0) | 2021.12.29 |
줄세우기 - 2631번 (0) | 2021.12.28 |
그대, 그머가 되어 - 14496번 (0) | 2021.12.27 |