最长路径问题

• 题目描述
  现有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

### 计算每一行可能存在的路径起点终点以及对应的路径长度，不同行中出现的同样起点和终点的路径保留长度最大的    
def v2v(strs):
    d={}
    for s in strs:
        for i in range(0,len(s)-2,2):
            for j in range(i+2,len(s),2):
                key = s[i]+s[j]
                value = sum([int(s[k]) for k in range(i+1,j,2) ])
                if key not in d.keys() or value > d[key]:
                    d[key] = value
                else :
                    pass
    return d

### 判断是否存在环
def is_ring(d):
    s=[]
    for key in d.keys():
        v2v=key[1]+key[0]
        s.append(v2v)
    m=set(s)&set(d.keys())
    if len(m) > 0:
        return 1
    else:
        return 0

### 将能够连接的路径相连合并
def road_join(d):
    keys=list(d.keys())
    values=list(d.values())
    flag=0    
    for i in range(len(keys)):
        for j in range(len(keys)):
            if keys[i][1]==keys[j][0]:
                new_key=keys[i][0]+keys[j][1]
                new_value=values[i]+values[j]
                if new_key not in keys:
                    d[new_key]=new_value
                    flag=1
                elif new_value > d[new_key]:
                    d[new_key]=new_value
                    flag=1
                else:
                    pass
    if flag==1:
        road_join(d)
 
def calculate(M,strs):
    d=v2v(strs)
    flag=is_ring(d)
    if flag==1:
        return -1
    else:
        road_join(d)
        return max(d.values())

##################################       
            
M = int(input())
strs_cnt = M
strs_i =0
strs = []
while strs_i <= strs_cnt:
    strs_item = input()
    strs.append(strs_item)
    strs_i +=1

res = calculate(M,strs)