Aizu Online Judge 0144 Packet Transportation

■0144 Packet Transportation

BFSするだけ．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n;  
17.  int start, goal, ttl;  
18.  LinkedList<Integer>[] graph;  
19.   
20.  @SuppressWarnings("unchecked")  
21.  void run(){  
22.   n=sc.nextInt();  
23.   graph=new LinkedList[n];  
24.   for(int j=0; j<n; j++){  
25.    int u=sc.nextInt()-1;// ルータ番号  
26.    int m=sc.nextInt();  
27.    graph[u]=new LinkedList<Integer>();  
28.    for(int i=0; i<m; i++){  
29.     int v=sc.nextInt()-1;  
30.     graph[u].add(v);  
31.    }  
32.   }  
33.   int p=sc.nextInt();  
34.   for(int i=0; i<p; i++){  
35.    start=sc.nextInt()-1;  
36.    goal=sc.nextInt()-1;  
37.    ttl=sc.nextInt();  
38.    solve();  
39.   }  
40.  }  
41.   
42.  void solve(){  
43.   LinkedList<Integer> que=new LinkedList<Integer>();  
44.   boolean[] visited=new boolean[n];  
45.   int[] d=new int[n];  
46.   Arrays.fill(d, INF);  
47.   que.offer(start);  
48.   d[start]=1;  
49.   visited[start]=true;  
50.   for(; !que.isEmpty();){  
51.    int u=que.poll();  
52.    for(int v : graph[u]){  
53.     if(!visited[v]){  
54.      que.offer(v);  
55.      d[v]=d[u]+1;  
56.      visited[v]=true;  
57.     }  
58.    }  
59.   }  
60.   if(d[goal]<=ttl){  
61.    println(""+d[goal]);  
62.   }else{  
63.    println("NA");  
64.   }  
65.  }  
66.   
67.  void debug(Object... os){  
68.   System.err.println(Arrays.deepToString(os));  
69.  }  
70.   
71.  void print(String s){  
72.   System.out.print(s);  
73.  }  
74.   
75.  void println(String s){  
76.   System.out.println(s);  
77.  }  
78.   
79.  public static void main(String[] args){  
80.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
81.   new Main().run();  
82.  }  
83. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int start, goal, ttl;
 LinkedList<Integer>[] graph;

 @SuppressWarnings("unchecked")
 void run(){
  n=sc.nextInt();
  graph=new LinkedList[n];
  for(int j=0; j<n; j++){
   int u=sc.nextInt()-1;// ルータ番号
   int m=sc.nextInt();
   graph[u]=new LinkedList<Integer>();
   for(int i=0; i<m; i++){
    int v=sc.nextInt()-1;
    graph[u].add(v);
   }
  }
  int p=sc.nextInt();
  for(int i=0; i<p; i++){
   start=sc.nextInt()-1;
   goal=sc.nextInt()-1;
   ttl=sc.nextInt();
   solve();
  }
 }

 void solve(){
  LinkedList<Integer> que=new LinkedList<Integer>();
  boolean[] visited=new boolean[n];
  int[] d=new int[n];
  Arrays.fill(d, INF);
  que.offer(start);
  d[start]=1;
  visited[start]=true;
  for(; !que.isEmpty();){
   int u=que.poll();
   for(int v : graph[u]){
    if(!visited[v]){
     que.offer(v);
     d[v]=d[u]+1;
     visited[v]=true;
    }
   }
  }
  if(d[goal]<=ttl){
   println(""+d[goal]);
  }else{
   println("NA");
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}