ACM-ICPC 2010 国内予選問題 Problem E 最強の呪文

Problem E 最強の呪文

動的計画法。各ノードiについてそれぞれの長さlの呪文で最強のものを覚えておく。そのような呪文をS_i,lとすると、
S_i,l = min_{s∈{t|y_t=i}}(S_{x_s,l-|lab_s|}+lab_s)
が成り立つ。と、 id:pes_magic が言っていた。

最強の呪文が存在しない２つめの場合。文字列u,w,vについて、uw²v < uwvが成り立つならば、任意のkについて、uw^k+1v < uw^kvが成り立つので、最強の呪文はループを含まない。最強の呪文が経由する各ノードからは同じ矢印で出るので、最強の呪文の長さは高々6(n-1)。長さ2・6(n-1)まで調べれば、最強の呪文が存在しない場合に、6(n-1)よりも長い呪文が、強い呪文として見つかるはず。たぶん。

ジャッジデータに、スレイヤーズと魔法使いサリーがあった。

E2:tasogareyorimokurakimonochinonagareyoriakakimono
E3:maharikumaharitayanbarayanyanyan
E4:acmicpctokyo

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    while ( true )
    {
        int n, a, s, g;
        cin >> n >> a >> s >> g;
        if ( n == 0  &&  a == 0  &&  s == 0  &&  g == 0 )
            break;

        vector<int> x( a );
        vector<int> y( a );
        vector<string> lab( a );
        for ( int i=0; i<a; i++ )
            cin >> x[i] >> y[i] >> lab[i];

        int     N = 6*(n-1);    //  ループしない呪文の最大長
        string  inf( N, 'z' );  //  "zzzzzz..."

        vector<vector<string> > spell( n, vector<string>( 2*N+1, inf ) );
        spell[s][0] = "";

        for ( int l=0; l<2*N; l++ )
        for ( int i=0; i<n; i++ )
        if ( spell[i][l] != inf )
        {
            for ( int j=0; j<a; j++ )
            if ( x[j] == i )
            {
                string sp = spell[i][l] + lab[j];
                int len = (int)sp.length();

                if ( len <= 2*N )
                    spell[y[j]][len] = min( spell[y[j]][len], sp );
            }
        }

        string ans = *min_element( spell[g].begin(), spell[g].end() );

        if ( ans != inf  &&
             (int)ans.length() <= N )
            cout << ans << endl;
        else
            cout << "NO" << endl;
    }
}