Submission #1609615


Source Code Expand

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.bitmanip;  // BitArray

alias graph = Graph!(int, size_t);

void main()
{
  auto rd1 = readln.split.to!(size_t[]), n = rd1[0], m = rd1[1];

  struct Edge { size_t a, b; int c; }

  auto e = new Edge[](m);
  auto g = new int[][](n, n);
  foreach (i; 0..n) {
    g[i][] = graph.inf;
    g[i][i] = 0;
  }

  foreach (i; 0..m) {
    auto rd2 = readln.splitter;
    auto a = rd2.front.to!size_t-1; rd2.popFront();
    auto b = rd2.front.to!size_t-1; rd2.popFront();
    auto c = rd2.front.to!int;
    e[i] = Edge(a, b, c);
    g[a][b] = g[b][a] = c;
  }

  auto d = graph.floydWarshal(g);

  auto ans = BitArray();
  ans.length = m;

  foreach (i; 0..n)
    foreach (j; 0..m) {
      auto a = e[j].a, b = e[j].b, c = e[j].c;
      if (d[i][a] + c == d[i][b] || d[i][b] + c == d[i][a])
        ans[j] = true;
    }

  writeln(m - ans.bitsSet.walkLength);
}

template Graph(Wt, Node, Wt _inf = 10 ^^ 9, Node _sent = Node.max)
{
  import std.algorithm, std.array, std.conv;

  const inf = _inf, sent = _sent;

  Wt[][] floydWarshal(Wt[][] g)
  {
    Wt[][] dist;
    Node[][] inter;
    floydWarshal(g, dist, inter);
    return dist;
  }

  void floydWarshal(Wt[][] g, out Wt[][] dist, out Node[][] inter)
  {
    auto n = g.length;
    dist = g.map!(i => i.dup).array;

    inter = new Node[][](n, n);
    foreach (i; 0..n) inter[i][] = sent;

    foreach (k; 0..n)
      foreach (i; 0..n)
        foreach (j; 0..n)
          if (dist[i][j] > dist[i][k] + dist[k][j]) {
            dist[i][j] = dist[i][k] + dist[k][j];
            inter[i][j] = k.to!Node;
          }
  }
}

Submission Info

Submission Time
Task D - Candidates of No Shortest Paths
User tesh
Language D (DMD64 v2.070.1)
Score 400
Code Size 1718 Byte
Status AC
Exec Time 5 ms
Memory 508 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 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 380 KB
subtask_1_03.txt AC 3 ms 508 KB
subtask_1_04.txt AC 3 ms 508 KB
subtask_1_05.txt AC 4 ms 508 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 2 ms 380 KB
subtask_1_08.txt AC 3 ms 508 KB
subtask_1_09.txt AC 3 ms 508 KB
subtask_1_10.txt AC 3 ms 508 KB
subtask_1_11.txt AC 1 ms 256 KB
subtask_1_12.txt AC 2 ms 380 KB
subtask_1_13.txt AC 3 ms 508 KB
subtask_1_14.txt AC 3 ms 508 KB
subtask_1_15.txt AC 3 ms 508 KB
subtask_1_16.txt AC 1 ms 256 KB
subtask_1_17.txt AC 1 ms 256 KB
subtask_1_18.txt AC 1 ms 380 KB
subtask_1_19.txt AC 2 ms 380 KB
subtask_1_20.txt AC 1 ms 256 KB
subtask_1_21.txt AC 1 ms 256 KB
subtask_1_22.txt AC 2 ms 380 KB
subtask_1_23.txt AC 2 ms 380 KB
subtask_1_24.txt AC 4 ms 508 KB
subtask_1_25.txt AC 2 ms 380 KB
subtask_1_26.txt AC 3 ms 508 KB
subtask_1_27.txt AC 5 ms 508 KB
subtask_1_28.txt AC 4 ms 508 KB