携程2018春招-大数据分析师在线笔试题-最长路径问题

最长路径问题

题目描述
现有A、B、C、D、E五个字符，以及M个字符串，每个字符串由这五个字符和1-9的整数间隔组成，
如：A2B3D，表示存在A->B 和 B->D的路径，且路径长度为2和3，可以推出A->D的一条路径长为5；
求最长的一条路径的长度，如果任何一处路径出现环（即出现A->···->A,B->···->B,C->···->C,D->···->D,E->···->E的路径，返回-1）

输入：
第一行为字符串的个数M
第二行开始为M个字符串
输出：
最长的一条路径的长度，如果出现环，返回-1

样例输入：
4
A2B3D
A4C2E
A5D
C3B

样例输出：

10
*********************************************************************************************************************
本人菜鸟，感觉应该是有向带权图的最长路径。
图这块我完全不会，所以做不来……
求大神来解答一番。
样例里就是A-4-C-3-B-3-D