結果

問題 No.614 壊れたキャンパス
ユーザー ikd
提出日時 2017-12-14 16:43:18
言語 D
(dmd 2.109.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 3
権限があれば一括ダウンロードができます

ソースコード

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();
    }
  }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0