【大意】
给定一个 CNF 和一个有向图。有向图上的每一条边都写上了一个字母。
要求你从 \(s\) 到 \(t\) 走一条尽可能短的路，且将经过的字母写下来后，这个字符串能被 CNF 接受。
输出字符串的串长。
【分析】
在有向图上行走，并写下边上的字符，这个过程等价于一个 DFA：
将所有状态的所有没提到过的其他字符全部指向一个状态，然后 \(s\) 为起始状态，\(t\) 为接受状态集里的唯一状态。
于是问题变化成了，给定一个 CNF 的 CFG 和一个 DFA ，求两者交集的 CFG 生成的最短串的串长。
关于生成该交集的 CFG 的方法，在本人的 上一篇博客 中有比较详细的说明。现在问题化为，给定一个 CFG ，怎么求它派生出的最短串长。
标签：状态,有向图,Grammar,Northern,题解,串长,CNF,给定,CFG From： https://www.cnblogs.com/JustinRochester/p/17091357.html