https://www.acmicpc.net/problem/10282
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n; // ์ปดํจํฐ ๊ฐ์
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int testCase = Integer.parseInt(br.readLine());
StringTokenizer st;
for (int i=0; i<testCase; i++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken()); // ์์กด์ฑ ๊ฐ์
int c = Integer.parseInt(st.nextToken()); // ํดํน๋นํ ์ปดํจํฐ
// Computer์ถ๊ฐ
ArrayList<Computer> computerList = new ArrayList<>();
computerList.add(new Computer(0)); // Index๋ฅผ ๋ง์ถ๊ธฐ ์ํด ์ถ๊ฐ
for (int j=1; j<=n; j++) {
computerList.add(new Computer(i));
}
// ์์กด์ฑ ์ถ๊ฐ
// b๊ฐ ๊ฐ์ผ๋๋ฉด s์ดํ์ a๊ฐ ๊ฐ์ผ
for (int j=0; j<d; j++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
computerList.get(b).dependency.put(a, s);
}
bw.write(dijkstra(computerList, c) +" ");
// ๊ฐ์ฅ ์ค๋๊ฑธ๋ฆฐ ์๊ฐ ํ์
int maxTime = -1;
for (int j=1; j<=n; j++) {
if (maxTime < computerList.get(j).time && computerList.get(j).time != Integer.MAX_VALUE) {
maxTime = computerList.get(j).time;
}
}
bw.write(maxTime + "\n");
}
bw.flush();
bw.close();
}
static int dijkstra (ArrayList<Computer> computerList, int c) {
Queue<Integer> queue = new LinkedList<>();
queue.add(c);
computerList.get(c).time = 0;
HashSet<Integer> set = new HashSet<>();
while (!queue.isEmpty()) {
int pop = queue.poll();
set.add(pop);
for (int key : computerList.get(pop).dependency.keySet()) {
// ์ฐ๊ฒฐ๋ node์ ์๊ฐ์ด ํ์ฌ node๊น์ง ์จ ์๊ฐ+์ฐ๊ฒฐ๋ node๊น์ง ๊ฐ๋ ์๊ฐ๋ณด๋ค ํฌ๋ค๋ฉด ๊ฐ์ ๋ณ๊ฒฝ
if (computerList.get(key).time > computerList.get(pop).dependency.get(key) + computerList.get(pop).time) {
computerList.get(key).time = computerList.get(pop).dependency.get(key) + computerList.get(pop).time;
queue.add(key);
}
}
}
return set.size();
}
}
class Computer {
int id;
int time;
HashMap<Integer, Integer> dependency;
public Computer(int id) {
this.id = id;
this.time = Integer.MAX_VALUE;
dependency = new HashMap<>();
}
}
ํด๋น ๋ฌธ์ ๋ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํ๋ ๋ฌธ์ ๋ก ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ๋ ์ ์๊ณ ๊ตฌํ์ ํ ์ ์๋ค๋ฉด ์ฝ๊ฒ ํ ์ ์๋ ๋ฌธ์ ์๋ค.
ํ์ง๋ง ๋ด๊ฐ ์์ฑํ ์ฝ๋์ ๊ฒฝ์ฐ๋ Computer๊ฐ์ฒด์์ ์ฐ๊ฒฐ๋ Computer์ ์ ๋ณด ๋ฐ ํด๋น ์ปดํจํฐ๊น์ง ์ค๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ ๋ฑ์ ์ ๋ณด๋ฅผ HashMap, ArrayList๋ฑ์ ์ฌ์ฉํ์ฌ ํ๋ฒ์ ๊ด๋ฆฌ๋ฅผ ํ๋ค๋ณด๋ ์คํ์๊ฐ ๋ฐ ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ๋์ด ๋ง์ ๊ฒ์ ๋ณผ ์ ์์๋ค.
๋ค์๋ถํฐ ์ฝ๋๋ฅผ ์์ฑํ ๋๋ ๋ฌด์กฐ๊ฑด ๊ฐ์ฒด์งํฅ์ผ๋ก ๊ฐ์ฒด๋ฅผ ๋ง๋ค์ด์ ์ฝ๋ฉ์ ํ๋ ๊ฒ์ด ์๋ ์ฌ๋ฌ๊ฐ์ ๋ฐฐ์ด์ ์ฌ์ฉํ์ฌ ์ฝ๋๋ฅผ ์์ฑํด๋ณด๋๋ก ํด์ผ๊ฒ ๋ค.