首页 > 试题广场 >

旅途

[编程题]旅途

热度指数：4282 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

原来是要到醋溜站台乘坐醋溜快车到醋溜港”，亮亮解出了地图隐藏的秘密，赶紧奔向醋溜站台，但到了之后，亮亮忧桑地发现，从醋溜站台到醋溜港沿途的每个车站都有很多美女被他飒爽的英姿所吸引，只要经过车站就会被这些漂亮的女孩搭讪，但是现在亮亮一心想要寻找楚楚街而没空去搭理她们，所以亮亮希望在抵达醋溜港的时候被搭讪的次数最少。问亮亮抵达醋溜港最少会被搭讪多少次？

输入描述:

第一行包含两个整数N(2<=N<=5000),M(1<=M<=50000)。N表示公有N个汽车站，M表示公有M条公路，起点为1，终点为N。 第二行包含N个整数(0<=K<=10000)，第i个整数表示在第i站有K个美女想要搭讪亮亮。 接下来M行，每行包含两个整数P(1<=P<=N),Q(1<=Q<=N),代表P,Q两个站是有班车直达的。

输出描述:

一个整数，即亮亮抵达醋溜港最少需要被搭讪的次数。

示例1

输入

输出

算法知识视频讲解

Python

新鲜菜鸡🐔

Python很极限啊，，第一次1500ms过，，优化下650ms，，emmmmmmm

try:
    while 1:
        import collections
        N,M =[int(x) for x in input().split()]
        n_list = [int(x) for x in input().split()]
        G = collections.defaultdict(dict)
        for i in range(M):
            s,e = [int(x) for x in input().split()]
            G[s][e] = n_list[e-1]
            G[e][s] = n_list[s-1]
        ans = [float('inf') for i in range(N+1)]
        ans[1] = n_list[0]
        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]<ans[temp_node]:
                    ans[temp_node] = ans[minv]+G[minv][temp_node]
            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

发表于 2018-07-10 10:55:46 回复(0)