博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
PAT 1076
阅读量:5284 次
发布时间:2019-06-14

本文共 2644 字,大约阅读时间需要 8 分钟。

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
> 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
cur_level = new LinkedList
(); 41 cur_level.add(start); 42 visited[start] = true; 43 44 while (!cur_level.isEmpty()){ 45 Queue
next_level = new LinkedList
(); 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
>(); 79 for (int i = 0; i < N; i++) 80 graph.add(new ArrayList
()); 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
res_arr = new ArrayList
(); 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++的編譯報錯好萌啊... 

转载于:https://www.cnblogs.com/EpisodeXI/p/4080070.html

你可能感兴趣的文章
2012-01-12 16:01 hibernate注解以及简单实例
查看>>
iOS8统一的系统提示控件——UIAlertController
查看>>
PAT甲级——1101 Quick Sort (快速排序)
查看>>
python创建进程的两种方式
查看>>
1.2 基础知识——关于猪皮(GP,Generic Practice)
查看>>
迭代器Iterator
查看>>
java易错题----静态方法的调用
查看>>
php建立MySQL数据表
查看>>
最简单的线程同步的例子
查看>>
旅途上看的电影和观后感
查看>>
Ztree异步树加载
查看>>
关于IE和火狐,谷歌,Safari对Html标签Object和Embed的支持问题
查看>>
poj3320 Jessica's Reading Problem(尺取思路+STL)
查看>>
分布式计算开源框架Hadoop介绍
查看>>
安卓平台接口剖析
查看>>
坏的事情不都会带来坏的结果
查看>>
RPC的基础:调研EOS插件http_plugin
查看>>
第二次团队冲刺第二天
查看>>
bzoj 2257 (JSOI 2009) 瓶子与燃料
查看>>
11)Java abstract class 和 interface
查看>>