航线_楚楚街笔试题

“呼！！终于到了，可是接下来要怎么走才能到达楚楚街港港呢？”亮亮在醋溜港直发愁。突然“啾”的一下，一只银色小船出现在亮亮的面前，上面坐着小精灵丹丹“又见面了，有什么可以帮助你的么？”小精灵向亮亮眨了眨眼睛，微笑着说。 “我想去楚楚街港，但我不知道要怎么走，请问你可以告诉我么？”亮亮按捺着激动的心情轻声问道。 “楚楚街港呀......那是个特别美好的地方”小精灵歪着头想了想，说“我只能告诉你大海上所有的航线，剩下的就只能靠你自己啦~” “只有所有的航线呀”，亮亮的内心再三挣扎，却又没有其他的办法。 “不管有多困难，我一定要达到楚楚街港，请你告诉我吧”亮亮坚定地对小精灵说。小精灵欣赏地点了点头，递给亮亮一张航线图，并叮嘱道“时限是1000天，一定要到哦~”，然后如来时一般“啾”的一声，消失了。亮亮现在迫切地想要抵达楚楚街港，请问亮亮最快能在第几天抵达楚楚街港呢？

一行包含两个整数N(2<=N<=500),M(1<=M<=2000)，用单个空格隔开。表示公有N个港，M条航线。起点为1，终点为N。接下来M行，每行包含五个整数P,Q(1<=P,Q<=n), K(1<=K<=1000), X,Y(0<=X,Y<=10000),代表P,Q两个港有航线并需要K天，并且该航线在第X天到第Y天天气恶劣不可通行。

try: while 1: import collections N,M =[int(x) for x in input().split()] G = collections.defaultdict(dict) for i in range(M): s,e,c,a,b = [int(x) for x in input().split()] G[s][e] = [c,a,b] G[e][s] = [c,a,b] ans = [float('inf') for i in range(N+1)] ans[1] = 1 book = set() remain = set([i for i in range(N+1)]) minv = 1 while len(book)<len(G.keys()): book.add(minv) remain.remove(minv) for temp_node in G[minv]: if temp_node in book: continue if ans[minv]+G[minv][temp_node][0]<=G[minv][temp_node][1]: if ans[minv]+G[minv][temp_node][0]<ans[temp_node]: ans[temp_node] = ans[minv] + G[minv][temp_node][0] elif ans[minv]>G[minv][temp_node][2]: if ans[minv]+G[minv][temp_node][0]<ans[temp_node]: ans[temp_node] = ans[minv] + G[minv][temp_node][0] else: if G[minv][temp_node][2]+G[minv][temp_node][0]+1<ans[temp_node]: ans[temp_node] = G[minv][temp_node][2] + G[minv][temp_node][0]+1 temp_add_node = float('inf') for i in remain: if ans[i]<temp_add_node: minv = i temp_add_node = ans[i] print(ans[-1]) except EOFError: pass

航线

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题