SRM 675 Div2 Medium ShortestPathWithMagic

解けなかったので解説見ながら写経

問題

SRM 675 - TopCoder Wiki

n個の点と各頂点から各頂点までの距離が与えられる. k個のポーションを持っており,ポーションを使うと,ある頂点からある頂点までの距離が半分になる. 任意の枝でポーションは高々1回しか使えない時,頂点0から頂点1までの最短経路を求める問題.

解答

公式の解説が正確でわかりやすい. ダイクストラ法で解くことを考える.

  • 任意のステップで頂点0から遷移した時の状態とその状態に到達できる最小コストを保持する.
  • 保持している状態から最小のコストの状態を選び,そこから遷移できる状態とそのコストを計算する.
  • この処理を繰り返すことで頂点0から到達できる全ての状態と,その状態に到達できる最小コストを計算することが出来る.
  • ここでいう状態は何かというと,どの頂点にいるかと,ポーションがいくつ残っているかである.
  • 任意の頂点間は移動可能であり,頂点間の移動で,ポーションは高々1個しか使えないので,状態の遷移は2n通りある.
  • つまり,O(nk)個の頂点,O(n2k)個の枝からなるグラフの最短路を求める問題と等価である.

以上を踏まえながらダイクストラ法で解く.

class ShortestPathWithMagic
{
public:
  double getTime(vector <string> dist, int k)
    {
      set<tuple<int, int, int> > queue;
      int d, v, r;
      int n = dist.size();
      int inf = 10000;
      vector<vector<int> > shortest(n, vector<int>(k+1, inf));
      auto push = [&](int d, int v, int r) {
        // cout << "shortest[" << v << "][" << r << "]=" << shortest[v][r] << endl;
        if (d < shortest[v][r]) {
          // cout << "shortest[" << v << "][" << r << "]=" << d << endl;
          shortest[v][r] = d;
          queue.insert(make_tuple(d, v, r));
        }
      };
      push(0, 0, k);
      // cout << "queue.size()=" << queue.size() << endl;
      while(!queue.empty()) {
        auto it = queue.begin();
        tie(d,v,r) = *it;
        // cout << "(d,v,r)=(" << d << "," << v << "," << r << ")" << endl;
        queue.erase(it);
        for(int i = 0; i < n; i++){
          if (r > 0) {
            // cout << "use potion" << endl;
            push(d + dist[v][i] - '0', i, r-1);
          }
            // cout << "don't use potion" << endl;
          push(d +  2 * (dist[v][i] - '0'), i, r);
        }
        // cout << endl;
      }
      int minv = shortest[1][k];
      for(int i = 0; i < k; i++)minv= min(minv, shortest[1][i]);
      return (double)minv / 2.0;
    }
};