SRM471 Div1 Medium

500
最短経路。
足して13で割れるかどうかさえ記憶しておけば充分なので、ビットに押し込んで覚えておく。
(辺の重み%13)だけ左シフトし、(辺の重み%13)をORていけば記憶できる。
はみ出た分は下位ビットへ循環。


誤読して悲しい思いをした。

struct S {
  int node;
  int bit;
  int cost;
  S (int n, int b, int c) : node(n), bit(b), cost(c) {}
};
bool operator < (const S &a, const S &b)
{
  return a.cost > b.cost;
}

const int inf = 1 << 25;

int conv(char c)
{
  if ('A' <= c && c <= 'Z') return c - 'A' + 1;
  if ('a' <= c && c <= 'z') return c - 'a' + 27;
  return inf;
}

class ThirteenHard {
public:
  int calcTime(vector <string> C)
  {
    const int N = C.size();
    const int T = 1 << 13;

    int g[N][N];
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        g[i][j] = conv(C[i][j]);
      }
    }

    int cost[N][T];
    fill(&cost[0][0], &cost[N - 1][T], inf);

    priority_queue<S> q;
    q.push(S(0, 0, 0));
    while (q.size()) {
      S s = q.top();
      q.pop();
      if (cost[s.node][s.bit] != inf) continue;
      cost[s.node][s.bit] = s.cost;
      for (int i = 0; i < N; ++i) {
        int c = g[s.node][i];
        if (c == inf) continue;
        
        int b = s.bit;
        for (int shift = c % 13; shift--; ) {
          b <<= 1;
          if (b & (1 << 13)) {
            b ^= (1 << 13);
            b ^= 1;
          }
        }

        b |= 1 << (c % 13);
        if (b & 1) ; else q.push(S(i, b, s.cost + c));
      }
    }

    int ret = inf;
    for (int i = 1; i < T; ++i) {
      ret = min(ret, cost[N - 1][i]);
    }
    return ret == inf ? -1 : ret;
  }

};