携程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
最长路径问题
题目描述
现有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
全部评论
相关推荐