Submission #1127506


Source Code Expand

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        int n = 0, m = 0;
        Edge[][] edges = new Edge[0][0];
        String[] elems;
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            elems = br.readLine().split(" ");
            n = Integer.parseInt(elems[0]);
            m = Integer.parseInt(elems[1]);
            edges = new Edge[n][n];
            for (int i = 0; i < m; i++) {
                elems = br.readLine().split(" ");
                int from = Integer.parseInt(elems[0]);
                int to = Integer.parseInt(elems[1]);
                int cost = Integer.parseInt(elems[2]);
                Edge e = new Edge(cost);
                edges[from-1][to-1] = e;
                edges[to-1][from-1] = e;
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        for (int i = 0; i < n; i++) {
            Queue<Node> queue = new PriorityQueue<>((s1, s2) ->
                    Integer.compare(s1.totalCost, s2.totalCost));
            int[] dist = new int[n];
            for (int j = 0; j < n; j++){
                dist[j] = Integer.MAX_VALUE;
            }
            dist[i] = 0;
            Node start = new Node(i, 0, 0);
            Node[] result = new Node[n];
            queue.add(start);
            while (!queue.isEmpty()) {
                Node trg = queue.poll();
                if (dist[trg.current] != trg.totalCost)
                    continue;
                int current = trg.current;
                result[current] = trg;
                for (int j = 0; j < n; j++){
                    if(edges[current][j] == null)
                        continue;
                    int tmp = trg.totalCost + edges[current][j].cost;
                    if (dist[j] > tmp) {
                        queue.add(new Node(j, current, tmp));
                        dist[j] = tmp;
                    }
                }
            }
            for (Node node:result) {
                int current = node.current;
                int prev = node.prev;
                if (prev == 0)
                    continue;
                edges[prev][current].check = true;
            }
        }
        int sum = 0;
        for (Edge[] es:edges)
            for (Edge e:es) {
                if (e == null) continue;
                if (!e.check) sum++;
            }
        System.out.println(sum / 2);
    }
}

class Node {
    int prev;
    int current;
    int totalCost;
    Node (int i, int prev, int totalCost) {
        this.prev = prev;
        current = i;
        this.totalCost = totalCost;
    }

    Node (int current) {
        this.current = current;
    }
}

class Edge {
    int cost;
    boolean check;
    public Edge (int cost) {
        this.cost = cost;
        check = false;
    }
}

Submission Info

Submission Time
Task D - Candidates of No Shortest Paths
User nmjiri
Language Java8 (OpenJDK 1.8.0)
Score 400
Code Size 3146 Byte
Status AC
Exec Time 220 ms
Memory 28372 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 30
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt
Case Name Status Exec Time Memory
sample_01.txt AC 176 ms 26452 KB
sample_02.txt AC 154 ms 26452 KB
subtask_1_01.txt AC 152 ms 26196 KB
subtask_1_02.txt AC 165 ms 23892 KB
subtask_1_03.txt AC 175 ms 26196 KB
subtask_1_04.txt AC 179 ms 24796 KB
subtask_1_05.txt AC 202 ms 24916 KB
subtask_1_06.txt AC 152 ms 25940 KB
subtask_1_07.txt AC 163 ms 26068 KB
subtask_1_08.txt AC 189 ms 26580 KB
subtask_1_09.txt AC 180 ms 23636 KB
subtask_1_10.txt AC 182 ms 26820 KB
subtask_1_11.txt AC 159 ms 24788 KB
subtask_1_12.txt AC 171 ms 26068 KB
subtask_1_13.txt AC 191 ms 24148 KB
subtask_1_14.txt AC 180 ms 25172 KB
subtask_1_15.txt AC 184 ms 28372 KB
subtask_1_16.txt AC 157 ms 25684 KB
subtask_1_17.txt AC 159 ms 24532 KB
subtask_1_18.txt AC 164 ms 25556 KB
subtask_1_19.txt AC 195 ms 26580 KB
subtask_1_20.txt AC 157 ms 25044 KB
subtask_1_21.txt AC 150 ms 26068 KB
subtask_1_22.txt AC 173 ms 25684 KB
subtask_1_23.txt AC 168 ms 24404 KB
subtask_1_24.txt AC 201 ms 26836 KB
subtask_1_25.txt AC 187 ms 23764 KB
subtask_1_26.txt AC 197 ms 26708 KB
subtask_1_27.txt AC 220 ms 24788 KB
subtask_1_28.txt AC 201 ms 25812 KB