結果

問題 No.614 壊れたキャンパス
ユーザー ikdikd
提出日時 2017-12-14 17:10:47
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 877 ms / 2,000 ms
コード長 2,298 bytes
コンパイル時間 1,257 ms
コンパイル使用メモリ 133,164 KB
実行使用メモリ 55,860 KB
最終ジャッジ日時 2024-06-12 23:07:12
合計ジャッジ時間 11,104 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 793 ms
52,108 KB
testcase_09 AC 753 ms
55,612 KB
testcase_10 AC 631 ms
55,860 KB
testcase_11 AC 848 ms
52,284 KB
testcase_12 AC 877 ms
53,228 KB
testcase_13 AC 862 ms
54,716 KB
testcase_14 AC 828 ms
54,304 KB
testcase_15 AC 591 ms
52,608 KB
testcase_16 AC 740 ms
52,532 KB
testcase_17 AC 495 ms
51,776 KB
testcase_18 AC 581 ms
54,288 KB
testcase_19 AC 484 ms
43,680 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

  int n, m; long k; int 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 long[](vmax);
  const inf=1_000_000_000_000_000_000;
  fill(dist, inf);
  auto vis=new bool[](vmax);
  alias Node=Tuple!(int, "v", long, "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;
    if(vis[cur.v]) continue;
    vis[cur.v]=true; dist[cur.v]=cur.d;
    foreach(e; eds[cur.v]){
      if(dist[e.to]<=dist[cur.v]+e.cost) continue;
      Q.insert(Node(e.to, dist[cur.v]+e.cost));
    }
  }

  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