SRM524 Div2 Hard(1000) MultiplesWithLimit

MultiplesWithLimit

最初の例だと、1桁目は0で4が繰り上がる。2桁目は0で繰り上がるのは2か7。2が繰り上がっている場合は次に繰り上がるのは1か5……。頂点数Nの有向グラフを考えて、0, 1, ……, N-1を割り当てる。aが繰り上がっているときに制限を満たす数字を出力しつつbが繰り上がるならば、a→bに辺があるとする。このグラフ上で0から出発して0に戻ってくる最短閉路を求める。同じ長さの閉路が複数あるならば最後のほうの出力する数字が小さいものを選ぶ。

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

class MultiplesWithLimit{public:
string minMultiples( int N, vector <int> forbiddenDigits )
{
    bool F[10] = { false };
    for ( int i=0; i<(int)forbiddenDigits.size(); i++ )
        F[forbiddenDigits[i]] = true;

    vector<int> D(N,-1);
    vector<int> P(N);
    vector<char> R(N);
    queue<int> Q; Q.push(0);

    while ( !Q.empty() )
    {
        int v = Q.front();  Q.pop();
        for ( int i=v==0?1:0; i<10; i++ )
        {
            int t = N*i+v;
            if ( !F[t%10] &&
                 ( D[t/10]==-1 || D[t/10]==D[v]+1 && R[t/10]>'0'+t%10 ) )
            {
                D[t/10] = D[v]+1;
                P[t/10] = v;
                R[t/10] = '0'+t%10;
                Q.push(t/10);
            }
        }
    }

    if ( D[0]==-1 )
    {
        return "IMPOSSIBLE";
    }
    else
    {
        int m = 0;
        string ans;
        do
            ans += R[m],
            m = P[m];
        while ( m!=0 );

        if ( ans.length()<9 )
            return ans;
        else
        {
            char tmp[32];
            sprintf( tmp, "%s...%s(%d digits)",
                     ans.substr(0,3).c_str(),
                     ans.substr(ans.length()-3).c_str(),
                     ans.length() );
            return tmp;
        }
    }
}};