알고리즘/Dijkstra
BOJ - 10282 ) 해킹
개발자가될수있을까?
2020. 10. 30. 11:26
1717번: 집합의 표현
첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가
www.acmicpc.net
해킹당하는 컴퓨터의 개수와 시간을 구하기위해 다익스트라 알고리즘을 사용한다.
컴퓨터의 개수는 다익스트라알고리즘을 돌면서 만나는 노드의 개수이고,
시간은 다익스트라로 구한 최단경로중 길이가 가장 큰 것이다.
반례로, 아무컴퓨터와 연결되어있지 않은경우, 1대만 감염되어야 한다. 시간은 0초
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class 해킹 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int tc = Integer.parseInt(st.nextToken());
StringBuilder sb = new StringBuilder();
for(int i=0;i< tc;i++) {
int answer=0;
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken())-1;
ArrayList<int[]> node[] = new ArrayList[n];
for(int j=0;j<n;j++) {node[j] = new ArrayList<>();}
for(int j=0;j<d;j++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken())-1;
int b = Integer.parseInt(st.nextToken())-1;
int c = Integer.parseInt(st.nextToken());
node[b].add(new int[] {a,c});
}
int cost[] = new int[n];
for(int j=0;j<n;j++) cost[j] = 2147000000;
cost[s] =0;
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1]-o2[1];
}
});
pq.add(new int[] {s,0});
while(!pq.isEmpty()) {
int now[] = pq.poll();
if( cost[now[0]] < now[1]) continue;
int size = node[now[0]].size();
for(int j=0 ; j < size ; j++) {
int next[] = node[now[0]].get(j);
if(cost[next[0]] > cost[now[0]] + next[1]) {
cost[next[0]] = cost[now[0]] + next[1];
pq.add(new int[] {next[0] , cost[next[0]]});
}
}
}
int cnt=0;
for(int j=0; j<n ; j++) {
if( j != s && cost[j]!= 2147000000) answer = answer > cost[j] ? answer : cost[j];
if( cost[j]!= 2147000000) cnt++;
}
sb.append(cnt +" "+answer+"\n");
}System.out.println(sb);
}
}
