관리 메뉴

공부공간

BOJ - 10282 ) 해킹 본문

그래프 알고리즘/Dijkstra

BOJ - 10282 ) 해킹

SangwonSeo 개발자가될수있을까? 2020. 10. 30. 11:26
728x90


www.acmicpc.net/problem/10282

 

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);
	}

}

반례하나 못찾아서.. 단독으로 아무 컴퓨터랑 연결되어있지 않을때에 0을 출력해야한다.

728x90

'그래프 알고리즘 > Dijkstra' 카테고리의 다른 글

BOJ - 10282 ) 해킹  (0) 2020.10.30
BOJ - 1167 ) 트리의 지름  (0) 2020.10.25
BOJ - 1504 ) 특정한 최단 경로  (0) 2020.08.24
BOJ - 1261 ) 알고스팟  (0) 2020.04.16
BOJ - 1916 ) 최소비용 구하기  (0) 2020.04.16
BOJ - 1753 ) 최단경로  (0) 2020.04.07
0 Comments
댓글쓰기 폼