Submission #1728053


Source Code Expand

Copy
import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;

int INF = 999999999;

enum Color {
  WHITE = 0
  , GRAY
  , BLACK
}

struct Node {
  int u;
  int d;
  Color c;
  int p;
}

class Graph {
  Node[] nodes;
  int[][] mat;
  int u_start;

  this(int n, int[][] matrix, int u_start_with) {
    this.nodes = new Node[n];
    foreach (int i, ref Node node; nodes) {
      node.u = i + u_start_with;
      node.p = -1;
      node.c = Color.WHITE;
      node.d = INF;
    }
    this.u_start = u_start_with;
    this.mat     = matrix;
  }

  bool edge_exists(int row, int col) {
    row -= this.u_start;
    col -= this.u_start;
    if (this.mat[row][col] != -1) {
      return true;
    } else {
      return false;
    }
  }

  void dijkstra(int start) {

    this.nodes[start].d = 0;
    this.nodes[start].p = -1;

    while (true) {
      int mincost = INF;
      int next_u  = -1;

      foreach (ref Node node; this.nodes) {
        if (node.c != Color.BLACK && node.d < mincost) {
          mincost = node.d;
          next_u  = node.u;
          //writef("mincost = %d, next_u = %d\n", mincost, next_u);
        }
      }

      if (mincost==INF) {
        break;
      }

      this.nodes[next_u].c = Color.BLACK;

      foreach (int v, ref Node node; this.nodes) {
        if (node.c != Color.BLACK && edge_exists(next_u, v) && this.nodes[next_u].d + mat[next_u][v] < node.d) {
          node.d = this.nodes[next_u].d + mat[next_u][v];
          node.p = next_u;
          node.c = Color.GRAY;
          //writef("index: %d, node.u: %d\n", v, node.u);
        }
      }

      // end
    }
  }
}

void main()
{

  // START
  string lines;
  string buf;
  while (!stdin.eof) {
    buf = stdin.readln();
    lines ~= buf;
  }
  // END

//string lines = q"[5 5
//1 2 12
//2 3 14
//3 4 7
//4 5 9
//5 1 18]";
  string[] array = splitLines(lines);
  //writeln(to!string(array));

  int N = array[0].split(" ")[0].to!int;
  int M = array[0].split(" ")[1].to!int;
  int[][] mat = new int[][](N, N);

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      mat[i][j] = -1;
    }
  }

  for (int i = 1; i < M+1; i++) {
    int u = array[i].split(" ")[0].to!int;
    int v = array[i].split(" ")[1].to!int;
    int w = array[i].split(" ")[2].to!int;
    mat[u-1][v-1] = w;
    mat[v-1][u-1] = w;
  }

  Graph graph = new Graph(N, mat, 0);
  int[] max_array = new int[](N);

  foreach (int n, ref int elem; max_array) {
    Graph g = new Graph(N, mat, 0);
    g.dijkstra(n);
    elem = g.nodes.map!(node => node.d).reduce!(max);
  }

  writeln(reduce!(min)(max_array));
}

Submission Info

Submission Time
Task D - バスと避けられない運命
User hiroyuking
Language D (DMD64 v2.070.1)
Score 100
Code Size 2756 Byte
Status
Exec Time 262 ms
Memory 12540 KB

Test Cases

Set Name Score / Max Score Test Cases
All 100 / 100 sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
test_01.txt 1 ms 256 KB
test_02.txt 176 ms 4732 KB
test_03.txt 262 ms 12540 KB
test_04.txt 74 ms 3964 KB
test_05.txt 88 ms 4476 KB
test_06.txt 12 ms 1404 KB
test_07.txt 194 ms 11900 KB
test_08.txt 2 ms 508 KB
test_09.txt 63 ms 2428 KB
test_10.txt 11 ms 1404 KB
test_11.txt 12 ms 1404 KB
test_12.txt 125 ms 3452 KB
test_13.txt 13 ms 1404 KB
test_14.txt 18 ms 1404 KB
test_15.txt 180 ms 11772 KB
test_16.txt 20 ms 1404 KB
test_17.txt 70 ms 2428 KB
test_18.txt 114 ms 3836 KB
test_19.txt 22 ms 1404 KB
test_20.txt 19 ms 1404 KB
test_21.txt 1 ms 256 KB
test_22.txt 49 ms 2172 KB
test_23.txt 2 ms 380 KB
test_24.txt 176 ms 4476 KB
test_25.txt 177 ms 3580 KB
test_26.txt 40 ms 3324 KB
test_27.txt 53 ms 1404 KB
test_28.txt 177 ms 3964 KB
test_29.txt 177 ms 3452 KB
test_30.txt 9 ms 636 KB
test_31.txt 2 ms 380 KB
test_32.txt 176 ms 3580 KB
test_33.txt 178 ms 4220 KB
test_34.txt 4 ms 508 KB
test_35.txt 31 ms 1148 KB
test_36.txt 177 ms 4476 KB