結果

問題 No.614 壊れたキャンパス
ユーザー ikdikd
提出日時 2017-12-14 16:43:18
言語 D
(dmd 2.106.1)
結果
WA  
実行時間 -
コード長 2,204 bytes
コンパイル時間 889 ms
コンパイル使用メモリ 129,600 KB
実行使用メモリ 55,228 KB
最終ジャッジ日時 2024-06-12 23:04:50
合計ジャッジ時間 9,918 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,944 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,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 763 ms
50,592 KB
testcase_09 AC 750 ms
53,032 KB
testcase_10 AC 624 ms
55,228 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 827 ms
52,636 KB
testcase_14 AC 754 ms
52,140 KB
testcase_15 AC 555 ms
52,928 KB
testcase_16 AC 694 ms
51,532 KB
testcase_17 WA -
testcase_18 AC 555 ms
49,952 KB
testcase_19 AC 484 ms
42,876 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

void main(){
  import std.stdio, std.string, std.conv, std.algorithm;

  int n, m, k, s, t; rd(n, m, k, s, t);
  s--; t--;
  auto as=new int[](m), from=new int[](m), to=new int[](m);
  foreach(i; 0..m)
    rd(as[i], from[i], to[i]), as[i]--, from[i]--, to[i]--;

  int[long] map;
  map[s]=0; map[(n-1)*k+t]=1;
  foreach(i; 0..m){
    if((as[i]*k+from[i] in map)==null) map[as[i]*k+from[i]]=map.length.to!int; 
    if(((as[i]+1)*k+to[i] in map)==null) map[(as[i]+1)*k+to[i]]=map.length.to!int; 
  }
  import std.typecons;
  alias Edge=Tuple!(int, "to", int, "cost");
  auto vmax=map.length;
  auto eds=new Edge[][](vmax, 0);
  foreach(i; 0..m){
    auto u=map[as[i]*k+from[i]],
         v=map[(as[i]+1)*k+to[i]];
    eds[u]~=Edge(v, 0);
  }
  auto blds=new int[][](n, 0);
  blds[0]~=s; blds[n-1]~=t;
  foreach(i; 0..m){
    blds[as[i]]~=from[i];
    blds[as[i]+1]~=to[i];
  }
  foreach(i; 0..n){
    auto b=blds[i];
    sort(b);
    for(auto j=0, pre=-1; j<b.length; j++){
      while(j+1<b.length && b[j]==b[j+1]) j++;
      if(pre>=0){
        auto u=map[i*k+b[pre]], v=map[i*k+b[j]];
        auto d=b[j]-b[pre];
        eds[u]~=Edge(v, d);
        eds[v]~=Edge(u, d);
      }
      pre=j;
    }
  }

  auto dist=new int[](vmax);
  const inf=1_000_000_000;
  fill(dist, inf);
  alias Node=Tuple!(int, "v", int, "d");
  import std.container;
  auto Q=new BinaryHeap!(Array!Node, "a.d>b.d");
  Q.insert(Node(map[s], 0)); dist[map[s]]=0;
  while(Q.length>0){
    auto cur=Q.front; Q.removeFront;
    foreach(e; eds[cur.v]){
      if(dist[e.to]<=dist[cur.v]+e.cost) continue;
      dist[e.to]=dist[cur.v]+e.cost;
      Q.insert(Node(e.to, dist[e.to]));
    }
  }

  auto d=dist[map[(n-1)*k+t]];
  if(d<inf) writeln(d);
  else writeln(-1);
}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}
void wr(T...)(T x){
  import std.stdio;
  foreach(e; x) stderr.write(e, " ");
  stderr.writeln();
}
void prtup(T)(T tup){
  import std.stdio;
  foreach(i, e; tup){
    stderr.writeln(i);
    foreach(ee; e){
      foreach(eee; ee) stderr.write(eee, " ");
      stderr.writeln();
    }
  }
}
0