首页 > 代码库 > 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