結果

問題 No.614 壊れたキャンパス
ユーザー te-shte-sh
提出日時 2017-12-14 10:25:03
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 749 ms / 2,000 ms
コード長 2,220 bytes
コンパイル時間 860 ms
コンパイル使用メモリ 128,984 KB
実行使用メモリ 102,936 KB
最終ジャッジ日時 2024-06-12 23:04:15
合計ジャッジ時間 9,381 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 663 ms
86,004 KB
testcase_09 AC 678 ms
85,104 KB
testcase_10 AC 583 ms
94,424 KB
testcase_11 AC 711 ms
81,300 KB
testcase_12 AC 749 ms
81,724 KB
testcase_13 AC 748 ms
81,676 KB
testcase_14 AC 700 ms
89,548 KB
testcase_15 AC 562 ms
90,168 KB
testcase_16 AC 643 ms
86,644 KB
testcase_17 AC 439 ms
102,936 KB
testcase_18 AC 531 ms
72,832 KB
testcase_19 AC 478 ms
70,284 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.math;      // math functions

alias graph = Graph!(long, int, 10L^^18);
alias edge = graph.Edge;

void main()
{
  auto rd = readln.split.to!(int[]), n = rd[0], m = rd[1], k = rd[2], s = rd[3], t = rd[4];

  struct Rouka { int a, b, c; }
  auto roukas = new Rouka[](m);
  foreach (i; 0..m) {
    auto rd2 = readln.splitter;
    auto a = rd2.front.to!int-1; rd2.popFront();
    auto b = rd2.front.to!int;   rd2.popFront();
    auto c = rd2.front.to!int;
    roukas[i] = Rouka(a, b, c);
  }

  auto r = new int[][](n);
  foreach (rouka; roukas) {
    r[rouka.a] ~= rouka.b;
    r[rouka.a+1] ~= rouka.c;
  }
  r[0] ~= s;
  r[$-1] ~= t;

  foreach (ri; r) ri.sort();

  auto h = new int[int][](n), cnt = 0;
  foreach (i, ri; r)
    foreach (rij; ri)
      h[i][rij] = cnt++;

  auto g = new edge[][](cnt);

  foreach (i, ri; r)
    if (ri.length >= 2)
      foreach (j; 0..ri.length-1) {
        auto u = h[i][ri[j]], v = h[i][ri[j+1]], w = ri[j+1]-ri[j];
        g[u] ~= edge(u, v, w);
        g[v] ~= edge(v, u, w);
      }

  foreach (rouka; roukas) {
    auto u = h[rouka.a][rouka.b], v = h[rouka.a+1][rouka.c];
    g[u] ~= edge(u, v, 0);
  }

  auto dist = graph.dijkstra(g, h[0][s])[h[$-1][t]];

  writeln(dist == graph.inf ? -1 : dist);
}

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

  const inf = _inf, sent = _sent;

  struct Edge
  {
    Node src, dst;
    Wt wt;
  }

  Wt[] dijkstra(Edge[][] g, Node s)
  {
    Wt[] dist;
    Node[] prev;
    dijkstra(g, s, dist, prev);
    return dist;
  }

  void dijkstra(Edge[][] g, Node s, out Wt[] dist, out Node[] prev)
  {
    auto n = g.length;

    dist = new Wt[](n);
    dist[] = inf;
    dist[s] = 0;

    prev = new Node[](n);
    prev[] = sent;

    auto q = heapify!("a.wt > b.wt")(Array!Edge(Edge(sent, s, 0)));
    while (!q.empty) {
      auto e = q.front; q.removeFront();
      if (prev[e.dst] != sent) continue;
      prev[e.dst] = e.src;
      foreach (f; g[e.dst]) {
        auto w = e.wt + f.wt;
        if (dist[f.dst] > w) {
          dist[f.dst] = w;
          q.insert(Edge(f.src, f.dst, w));
        }
      }
    }
  }
}
0