아이디어

• 다익스트라로 각 정점까지의 최단비용을 구해야 한다.
• 시간복잡도: $n \leq 10\ 000$이므로 $O(n^2)$ 미만이어야 함
  • 우선순위 큐를 사용한 다익스트라 알고리즘(시간 복잡도: $O(n \lg n)$)
• INF가 아닌 정점의 개수와 그 중 최댓값을 출력하면 끝

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int T, n, d, c;
	static List<List<Edge>> graph = new ArrayList<>();
	static PriorityQueue<Edge> pq = new PriorityQueue<>();
	static int[] dist;
	
	public static void main(String[] args) throws Exception {
		T = Integer.parseInt(rd.readLine());
		for (int t=1; t<=T; t++) {
			tk = new StringTokenizer(rd.readLine());
			n = Integer.parseInt(tk.nextToken());
			d = Integer.parseInt(tk.nextToken());
			c = Integer.parseInt(tk.nextToken());
			
			graph.clear();
			for (int i=0; i<=n; i++) graph.add(new ArrayList<>());
			
			for (int i=0; i<d; i++) {
				tk = new StringTokenizer(rd.readLine());
				int a = Integer.parseInt(tk.nextToken());
				int b = Integer.parseInt(tk.nextToken());
				int s = Integer.parseInt(tk.nextToken());
				graph.get(b).add(new Edge(a, s));
			}
			
			dist = new int[n+1];
			
			// dijkstra with pq
			// c부터 시작
			Arrays.fill(dist, Integer.MAX_VALUE);
			dist[c] = 0;
			
			pq.offer(new Edge(c, 0));
			while (!pq.isEmpty()) {
				Edge e = pq.poll();
				int v = e.a;
				int c = e.s;
				if (dist[v] < c) continue;
				
				for (Edge ne: graph.get(e.a)) {
					int nv = ne.a;
					int nc = ne.s;
					if (dist[v] + nc < dist[nv]) {
						dist[nv] = dist[v] + nc;
						pq.offer(ne);
					}
				}
			}
			
			int cnt = 0;
			int max = 0;
			for (int i=1; i<=n; i++) {
				if (dist[i] != Integer.MAX_VALUE) {
					cnt++;
					max = Math.max(max, dist[i]);
				}
			}
			
			sb.append(cnt).append(' ').append(max).append('\n');
		}
		System.out.println(sb);
	}
	
	static class Edge implements Comparable<Edge>{
		int a, s;
		Edge(int a, int s) {
			this.a = a;
			this.s = s;
		}
		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.s, o.s);
		}
		
	}
}

메모리 및 시간

• 메모리: 168344 KB
• 시간: 1316 ms

리뷰

• 메모리 처리를 따로 해주지 않았는데 통과함
• 객체가 아닌 배열을 사용하거나 하는 등을 생각해보자.
• Dijkstra 익혀놓기!
  • 핵심 아이디어: 현재까지의 거리와 그 점을 경유했을 때의 거리를 비교 갱신