首页 > 代码库 > PAT 1076
PAT 1076
JAVA沒法玩系列,C++寫了是248ms,JAVA 3000ms的時間限制都TLE,我已經看到考PAT的時候自己沮喪的樣子了。
簡單的BFS。
1 import java.util.*; 2 import java.io.*; 3 4 class FastReader{ 5 BufferedReader reader; 6 StringTokenizer tokenizer; 7 8 FastReader(InputStream stream){ 9 reader = new BufferedReader(new InputStreamReader(stream), 1 << 20); 10 tokenizer = null; 11 } 12 13 String next(){ 14 while (tokenizer == null || !tokenizer.hasMoreTokens()){ 15 try { 16 tokenizer = new StringTokenizer(reader.readLine()); 17 } catch (Exception e){ 18 throw new RuntimeException(e); 19 } 20 } 21 22 return tokenizer.nextToken(); 23 } 24 25 int next_int(){ 26 return Integer.parseInt(next()); 27 } 28 } 29 30 public class Main { 31 static ArrayList<ArrayList<Integer>> graph; 32 33 static int bfs(int start, int level){ 34 int count = 0; 35 int level_cnt = 0; 36 37 Boolean[] visited = new Boolean[graph.size()]; 38 Arrays.fill(visited, false); 39 40 Queue<Integer> cur_level = new LinkedList<Integer>(); 41 cur_level.add(start); 42 visited[start] = true; 43 44 while (!cur_level.isEmpty()){ 45 Queue<Integer> next_level = new LinkedList<Integer>(); 46 47 while (!cur_level.isEmpty()){ 48 int cur_idx = cur_level.poll(); 49 50 for (Integer next_idx : graph.get(cur_idx)){ 51 if (visited[next_idx]) 52 continue; 53 54 next_level.add(next_idx); 55 visited[next_idx] = true; 56 count++; 57 } 58 } 59 60 level_cnt++; 61 if (level_cnt >= level) 62 break; 63 64 cur_level = next_level; 65 } 66 67 return count; 68 } 69 70 @SuppressWarnings("unused") 71 public static void main(String[] args){ 72 FastReader reader = new FastReader(System.in); 73 74 int N, L; 75 N = reader.next_int(); 76 L = reader.next_int(); 77 78 graph = new ArrayList<ArrayList<Integer>>(); 79 for (int i = 0; i < N; i++) 80 graph.add(new ArrayList<Integer>()); 81 82 for (int i = 0; i < N; i++){ 83 int num = reader.next_int(); 84 85 for (int j = 0; j < num; j++){ 86 int idx = reader.next_int(); 87 graph.get(idx - 1).add(i); 88 } 89 } 90 91 int K = reader.next_int(); 92 ArrayList<Integer> res_arr = new ArrayList<Integer>(); 93 for (int i = 0; i < K; i++){ 94 int idx = reader.next_int(); 95 int res = bfs(idx - 1, L); 96 97 res_arr.add(res); 98 } 99 100 for (Integer res : res_arr){101 System.out.println(res);102 }103 }104 }
下面刷題都用C++了,感覺clang++的編譯報錯好萌啊...
PAT 1076
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。