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'; } }
なぜか記事書いてなかった…