Submission #1629500
Source Code Expand
import java.util.*; public class Main { private static int N; private static int M; private static int r; private static int t; private static List<Edge>[] node; public static void input(){ Scanner scan = new Scanner(System.in); N = scan.nextInt(); M = scan.nextInt(); r = scan.nextInt(); t = scan.nextInt(); node = new List[N]; for(int i = 0;i < N;i++) node[i] = new ArrayList<>(); for (int i=0;i<M;i++){ int a = scan.nextInt() - 1; int b = scan.nextInt() - 1; int c = scan.nextInt(); node[a].add(new Edge(b,c)); node[b].add(new Edge(a,c)); } } static class Edge{ int to,dist; Edge(int to,int d){ this.to = to; dist = d; } } static int [] dijkstra(List<Edge>[] node,int s){ Queue<Pos> queue = new PriorityQueue<>(); queue.add(new Pos(s,0)); int[] dist = new int[node.length]; Arrays.fill(dist,Integer.MAX_VALUE); while(!queue.isEmpty()){ Pos p = queue.poll(); if(dist[p.id] < Integer.MAX_VALUE) continue; dist[p.id] = p.dist; for(Edge e: node[p.id]){ queue.add(new Pos(e.to,e.dist + p.dist)); } } Arrays.sort(dist); return dist; } static class Pos implements Comparable<Pos>{ int id,dist; Pos(int id,int d){ this.id = id; dist = d; } public int compareTo(Pos o){ return dist - o.dist; } } static int binarySearch(int []a,int v){ int l = 0, r = a.length - 1, s = -1; while(l <= r){ int m = (l + r)/2; if(a[m] >= v){ s = m; r = m - 1; }else l = m + 1; } return s; } public static void main(String args[]) { //入力 input(); long ans = 0; for(int i = 0;i < N;i++){ int dist[] = dijkstra(node,i); // 目的地(i)ごとに最短経路長のリストを求めてソート for(int j = 1 ;j < N;j++){ final int d = (int) ((dist[j] * r + t) / t); // カメの位置を固定 final int idx = binarySearch(dist,d); // ウサギは特定の最短経路長以上である if(idx < 0) break; ans += N - idx - (r < t ? 1 : 0); // カメがウサギより早い場合に注意 } } System.out.println(ans); } }
Submission Info
Submission Time | |
---|---|
Task | C - ウサギとカメ |
User | zaraki11 |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 2744 Byte |
Status | AC |
Exec Time | 2780 ms |
Memory | 154744 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample-01.txt, subtask0_sample-02.txt |
All | subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample-01.txt | AC | 125 ms | 20308 KB |
subtask0_sample-02.txt | AC | 102 ms | 19924 KB |
subtask1_01.txt | AC | 120 ms | 21588 KB |
subtask1_02.txt | AC | 114 ms | 21972 KB |
subtask1_03.txt | AC | 114 ms | 23508 KB |
subtask1_04.txt | AC | 103 ms | 20820 KB |
subtask1_05.txt | AC | 204 ms | 28332 KB |
subtask1_06.txt | AC | 253 ms | 32268 KB |
subtask1_07.txt | AC | 637 ms | 49092 KB |
subtask1_08.txt | AC | 479 ms | 45924 KB |
subtask1_09.txt | AC | 1185 ms | 91024 KB |
subtask1_10.txt | AC | 999 ms | 87056 KB |
subtask1_11.txt | AC | 837 ms | 61380 KB |
subtask1_12.txt | AC | 2226 ms | 152720 KB |
subtask1_13.txt | AC | 2242 ms | 151260 KB |
subtask1_14.txt | AC | 2534 ms | 92832 KB |
subtask1_15.txt | AC | 2018 ms | 150044 KB |
subtask1_16.txt | AC | 2780 ms | 154744 KB |