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