SRM 675 Div2 Medium ShortestPathWithMagic

ここ1ヶ月くらいサボりまくっていて久しぶりの SRM だった。
本番ナップザック的に DP でやれるんじゃないか？と思いつつも、i < j のとき j -> i へ移動するほうが最短な場合もあるし、だめかなーと思って幅優先っぽい手法で解いた。
本番最後の REP(i,k+1) が REP(i,k) にするというバグで時間を食ってしまった...。

class ShortestPathWithMagic {
public:
double getTime(vector <string> dist, int k) {
        int n = dist.size();

        const double inf = (1<<30);
        vector<vector<double>> d(n,vector<double>(k+1,inf));
#define cost(x,y) (dist[x][y]-'0')
        queue<tuple<int,int,double>> que;

        que.emplace(0,k,0);
        while ( !que.empty() )
        {
            double t;
            int kk;
            int x;
            tie(x,kk,t) = que.front();
            que.pop();

            REP(i,n)
            {
                if (x == i)
                    continue;
                if ( kk > 0 && t+cost(x,i)/2.0 < d[i][kk-1] )
                {
                    d[i][kk-1] = t+cost(x,i)/2.0;
                    que.emplace(i, kk-1, t+cost(x,i)/2.0);
                }
                if ( t+cost(x,i) < d[i][kk] )
                {
                    d[i][kk] = t+cost(x,i);
                    que.emplace(i, kk, t+cost(x,i));
                }
            }
        }
        double ret = inf;
        REP(i,k+1)
            ret = min(d[1][i],ret);
        return ret;
}
};

他の人のコードを見るに普通に DP で解けるのでそっちも実装してみた。普通に逆方向も見る全探索にすればいいだけだった。

class ShortestPathWithMagic {
public:
double getTime(vector <string> dist, int k) {
        int n = dist.size();
        const double inf = (1<<30);

        vector<vector<double>> d(n,vector<double>(k+1,inf));
#define cost(x,y) (dist[x][y]-'0')

        // Warshallfloyd で一旦最短経路を求めておく
        vector<vector<double>> g(n,vector<double>(n,inf));
        REP(i,n)
        REP(j,n)
            g[i][j] = cost(i,j);

        REP(l,n)
        REP(i,n)
        REP(j,n)
            g[i][j] = min(g[i][j], g[i][l]+g[l][j]);

        // DP で解く
        // dp[i][k] := 0 -> i まで到達するとき potion の使用量が k であるときの最短経路長
        vector<vector<double>> dp(n,vector<double>(k+1,inf));
        dp[0][0] = 0.0;

        // 全探索
        REP(kk,k+1)
        {
            // j を経由して i に行くときを計算
            REP(i,n)
            REP(j,n)
                dp[i][kk] = min(dp[i][kk], dp[j][kk] + g[j][i]);

            if ( kk == k )
                break;

            REP(i,n)
            REP(j,n)
                dp[i][kk+1] = min(dp[i][kk+1], dp[j][kk] + cost(j,i)/2.0);
        }

        double ret = inf;
        REP(kk,k+1)
            ret = min(ret,dp[1][kk]);
        return ret;
}
};