原题链接：https://codeforces.com/contest/2005/problem/C
看了教程发现都是用dp做的，在这里分享一个差不多的SPFA的思路（赛场上忘了Dijkstra不能有负边所以炸了）
时间复杂度与dp同样是O(nm)
形式化题意和翻译：
有n个长度为m的字符串，你可以选择或不选择来拼接它们，但是不能更改字符串的顺序。对于得到的最终字符串，在其中依次循环地寻找“narek”，每找到一个字母+1分，找到一个在“narek”中但不是当前要找的字母-1分，其他字母不得分。求最大分数。
先不考虑最后没选完完整的narek的问题。注意到对于每个字符串，我们可以O(nm)预处理出“如果当前要找的字母为ch，则选择了第i个字符串后我能获得多少分数收益”和“如果当前要找的字母为ch，则选择了第i个字符串后我要找的字母变成了什么”。分别设为val[ch][i]和become[ch][i]。
在预处理完这两个数组后，我们注意到对于每一个可能的字符串，都有可能的两种操作，选或不选。而这又与且仅与当前要找的是什么字母有关。于是，我们建立n*5个点来表示状态，每个点表示对于第i个字符串，要找ch时的状态。对于第i个字符串，依据选或不选，向其他点连接两条边，选的话从自身向下一个字符串且要找become[ch][i]时对应的点连边（因为选择后要找的字符改变了），边权为val[ch][i]；不选的话从自身向下一个字符串且要找ch时对应的点连边（没有选择新串那么要找的字符不变），边权为0。那么我们最大化分数的过程就是求出一条从起点到终点的最长路，这可以在SPFA里建负边来实现。我们的起点就是第一个字符串要找‘n’时对应的点。
然后考虑最终状态，设5个点表示看完最终字符串后，还要找字母ch的状态。如果我们没有找到完整的一个“narek”那么，我们在看完所有字符串后还要找的字母必然是‘a’、‘r’、‘e’、‘k’中的一个。并且我们在计算分数时会错误的把这些不完整的“narek”加上而不是减去，于是我们根据将对应的结尾状态所对应的点的距离值直接减少2倍的ch-1。然后我们求出最后五个点中距离最大的值，便是整张图的最长路，也就是所求的最大分数。
标签：分数,Lazy,ch,972,题解,字母,不选,字符串,narek From： https://www.cnblogs.com/Almond/p/18415007