AOJ 1169: The Most Powerful Spell

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1169

dp[i][j]:=j番目のnodeについた時、文字列の長さがiのもののうち辞書列最小のもの
を更新していきます。i<=N*12までdpを更新します。

最小の呪文が決まるときは辞書列最小文字列の長さN*6以下になりますが、決まらないと、N*6より長さが大きい文字列が得られるので、その場合はNOを返します。

ベルマンフォードの負のサイクルの見つけ方と同じですね。

int N, M, S, T;
 
string dp[500][50];
vector<ps> G[50];
 
const string inf(1, (char)('z' + 1));
 
void solve() {
    while(true) {
        cin >> N >> M >> S >> T;
        if(N == 0) break;
        rep(i, 0, N) {
            G[i].clear();
        }
        rep(i, 0, M) {
            int a, b;
            string str;
            cin >> a >> b >> str;
            G[b].push_back(ps(a, str));
        }
        rep(i, 0, N * 12 + 1) 
            rep(j, 0, N) dp[i][j] = inf;
        dp[0][S] = "";
        rep(i, 0, N * 12 + 1) {
            rep(j, 0, N) {
                rep(k, 0, (int)G[j].size()) {
                    int n = G[j][k].fst;
                    string s = G[j][k].sec;
                    int sz = s.size();
                    if(i - sz >= 0 && dp[i - sz][n] != inf) {
                        dp[i][j] = min(dp[i][j], dp[i - sz][n] + s);
                    }
                }
            }
        }
        string res = inf;
        rep(i, 0, N * 12 + 1) {
            if(res > dp[i][T]) {
                if(dp[i][T] == "") continue;
                if(i <= N * 6) {
                    res = dp[i][T];
                }
                else {
                    res = "NO";
                    break;
                }
            }
        }
        if(res == inf) res = "NO";
        cout << res << '\n';
    }
}

なぜか記事書いてなかった…