import java.io.*;
import java.util.*;
public class mor {
static ArrayList<Integer>[] adj;
public static void main(String[] args) throws IOException, FileNotFoundException {
// Scanner in = new Scanner(new File("seafaring.in"));
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
int K = in.nextInt();
adj = new ArrayList[N];
for(int i = 0; i < N; i++){
adj[i] = new ArrayList<>();
}
for(int i = 0; i < M; i++){
int a = in.nextInt() - 1;
int b = in.nextInt() - 1;
adj[a].add(b);
adj[b].add(a);
}
// check what the minimum odd path is and the minimum even path is
long[][][] distances = new long[N][N][2];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
Arrays.fill(distances[i][j], Long.MAX_VALUE);
}
}
for(int i = 0; i < N; i++){
PriorityQueue<State> pq = new PriorityQueue<>();
pq.add(new State(i, 0));
while(!pq.isEmpty()){
State curr = pq.poll();
if(distances[i][curr.position][(int) (curr.distance % 2)] < curr.distance){
continue;
}
for(int ap: adj[curr.position]){
if(curr.distance + 1 < distances[i][ap][(int) (curr.distance + 1)%2]){
distances[i][curr.position][(int) (curr.distance % 2)] = Math.min(curr.distance, distances[i][curr.position][(int) (curr.distance % 2)]);
pq.add(new State(ap, curr.distance + 1));
}
}
}
}
for(int i = 0; i < K; i++){
int start = in.nextInt() - 1;
int end = in.nextInt() - 1;
int dist = in.nextInt();
// System.out.println(Arrays.toString(distances[start][end]));
if(distances[start][end][dist % 2] <= dist && distances[start][end][dist % 2] != Long.MAX_VALUE){
System.out.println("TAK");
} else {
System.out.println("NIE");
}
}
}
public static class State implements Comparable<State>{
int position;
long distance;
public State(int position, long distance){
this.position = position;
this.distance = distance;
}
public int compareTo(State s){
return Long.compare(distance, s.distance);
}
}
}
Compilation message
Note: mor.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
122 ms |
10852 KB |
Output is correct |
2 |
Correct |
124 ms |
10476 KB |
Output is correct |
3 |
Incorrect |
137 ms |
10328 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
160 ms |
10808 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
680 ms |
16452 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
801 ms |
23936 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2857 ms |
39672 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1074 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1174 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1142 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1238 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1210 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |