AOJ 0244 Hot Spring Trip

解法

ダイクストラ法とメモ化探索を利用しました。
連続した2区間を保存しておき、メモ化探索しながらその地点から切符で答えを更新できるか伺います。
ゴール地点 nからダイクストラ法を使うことで、切符を利用して着いた地点からゴール地点までの最短コストが求まるので枝刈しやすいです。
あとは今までで最短のコストを見ながら枝刈します。

設計メモ

int[][] two_link : 連続した2点間。two_link[ from ][ to ] = 経由地点
int[][] adj : 隣接行列(対称行列)。データの入力を格納する。
int[] d_cost : ダイクストラ法による、n からindex への最短コスト
int ans : 今までで最短のコスト

e : 現在地点
sum : 再起して求めてきた合計コスト
枝刈やゴール地点に着いたときの処理
for( i : 1 ~ N )
  if( two_link[ e ][ i ] )
    ans = min( ans, sum + d_cost[ i ] );

for( i : 1 ~ N )
  if( adj[ e ][ i ] )
   再起へ...( i , sum + adj[ e ][ i ] )

ソースコード

import std.stdio : writeln;
import std.array;
import std.range;
import std.typecons;
import std.algorithm : max, min;

immutable INF = 1 << 27;
immutable N = 100;
int n, m;
int[ N + 1 ][ N + 1 ] adj;
int[ N + 1 ][ N + 1 ] two_link;

void init(){
  init_d_cost();
  init_two_link();
}

void init_two_link(){
  for( int i = 1; i <= n ; ++i ){
    for( int j = i + 1; j <= n ; ++j ){
      for( int k = 1; k <= n ; ++k ){
        if( adj[ i ][ k ] * adj[ k ][ j ] ){
          two_link[ i ][ j ] = two_link[ j ][ i ] = k;
        }
      }
    }
  }
}

int[ N + 1 ] d_cost;
void init_d_cost(){
  d_cost = repeat( INF ).take( N + 1 ).array;
  
  d_cost[ n ] = 0;
  int e = n;
  bool[ N + 1 ] done;
  while( e ){
    done[ e ] = true;
    
    for( int i = 1; i <= n; ++i ){
      if( !done[ i ] && adj[ e ][ i ] ){
        int res = d_cost[ e ] + adj[ e ][ i ];
        if( d_cost[ i ] > res ){
          d_cost[ i ] = res;
        }
      }
    }
    
    int min_ = INF;
    int min_idx = 0;
    for( int i = 1; i <= n; ++i ){
      if( !done[ i ] && min_ > d_cost[ i ] ){
        min_ = d_cost[ i ];
        min_idx = i;
      }
    }
    
    e = min_idx;
  }
}

int ans = INF;
bool[ N + 1 ] s_done;
int[ int ] s_note;
void search( int e, int sum ){
  if( e == n ){
    ans = min( ans, sum );
    return;
  }
  
  if( sum >= ans ){
    return;
  }
  
  if( ( e in s_note ) != null ){
    int res = s_note[ e ];
    if( sum >= res ){
      return;
    }
  }
  s_note[ e ] = sum;

  s_done[ e ] = true;
  
  for( int i = 1; i <= n; ++i ){
    if( two_link[ e ][ i ] ){
      int res = sum + d_cost[ i ];
      ans = min( ans, res );
    }
  }
  
  for( int i = 1; i <= n; ++i ){
    if( adj[ e ][ i ] ){
      if( !s_done[ i ] ){
        search( i, sum + adj[ e ][ i ] );
      }
    }
  }
  
  s_done[ e ] = false;
}

void main(){
  while( 1 ){
    n = next!int;
    m = next!int;
    if( ( n | m ) == 0 ){
      break;
    }
    
    ans = INF;
    adj = adj.init;
    two_link = two_link.init;
    s_done = s_done.init;
    s_note = s_note.init;
    
    foreach( i; m.iota ){
      int a = next!int;
      int b = next!int;
      int c = next!int;
      
      adj[ a ][ b ] = adj[ b ][ a ] = c;
    }
    
    init();
    search( 1, 0 );
    
    ans.writeln;
  }
}


import std.stdio : readln;
import std.conv : to;
import std.string : split, chomp;
import std.traits;
string[] input;
string delim = " ";
T next(T)()
in
{
  assert(hasNext());
}
out
{
  input.popFront;
}
body
{
  return input.front.to!T;
}

終わりに

小なりと大なりを間違えて泣きを見ました。設計もあやふやのまま書き出しちゃったし、反省が多く残りました(それ以前の問題な気もするけど...)。
また、メモ化で通るかなと恐る恐るだったのですが通ってしまいました。もっと自信持って提出したいなあ...。

(クソザコの私が言っても失礼なだけだけど若い方たちがさくっと解けてて格好いい...)

クラスメイトの方々が春休みにみんなで温泉旅行行こうって言っててすごく行きたい、