AtCoder Regular Contest 025

Submission #1629500

Source codeソースコード

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

Task問題 C - ウサギとカメ
User nameユーザ名 kenpachi
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 2744 Byte
File nameファイル名
Exec time実行時間 2780 ms
Memory usageメモリ使用量 154744 KB

Compiler messageコンパイルメッセージ

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample-01.txt,subtask0_sample-02.txt
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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