Div2 1000 Thirteen

駅駅間の所要時間が2次元配列で与えられる．(A-Zは1〜26，a-zは27〜52，#は通行不可)
目的地に達するまでに経由する駅においてスタートからの時間が13の倍数になってはいけない．(※)
0番の駅からN-1番の駅まで達するのに要する最短時間を求めよ．

(※)4駅で移動した時，各駅間の所要時間が順に T0, T1, T2 だとするとき，T0, T0+T1, T0+T1+T2 のいずれも 13 の倍数になってはいけない．

考え方

ダイクストラを[N][13]で行えばOK．というのも[13]の方は達成時間の(mod 13)で分類すればいいだけなので．[N-1][*]の更新がされた時点でreturnすれば大丈夫．

コード

#include <set>
#include <string>
#include <vector>
using namespace std;

struct Lap
{
  int time, city;
  Lap(int a, int b) : time(a), city(b) {}
};
bool operator<(const Lap& a, const Lap& b)
{
  if( a.time == b.time ) {
    return a.city < b.city;
  }
  return a.time < b.time;
}

class Thirteen
{
  int distance(char c)
  {
    if( 'A' <= c && c <= 'Z' ) return c - 'A' + 1;
    return c - 'a' + 27;
  }
public:
  int calcTime(vector <string> city)
  {
    const int N = city.size();
    vector< vector<int> > shortest(N, vector<int>(13, 99999));
    set<Lap> q;
    shortest[0][0] = 0;
    q.insert(Lap(0, 0));
    while( !q.empty() ) {
      Lap l = *q.begin();
      q.erase(q.begin());
      if( l.city == city.size() - 1 ) return l.time;
      string& dist = city[l.city];
      for( int i = 0 ; i < city.size() ; ++i ) {
        if( dist[i] == '#' ) continue;
        int tt = l.time + distance(dist[i]);
        int ff = tt % 13;
        if( ff == 0 ) continue;
        if( shortest[i][ff] > tt ) {
          shortest[i][ff] = tt;
          q.insert(Lap(tt, i));
        }
      }
    }
    return -1;
  }
};