携程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
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务