首页 > 大疆软件类B卷编程题 过2.9
头像
爱玩矢量
编辑于 2020-08-16 21:12
+ 关注

大疆软件类B卷编程题 过2.9

第一题

  • 无向图中两点的最短距离
  • 用的DFS,过了90
def first():
    n, p = map(int, input().strip().split(' '))
    cost = [[101] * n for _ in range(n)]
    for _ in range(p):
        x, y, t = map(int, input().strip().split(' '))
        cost[x][y] = t
        cost[y][x] = t
    end = int(input())

    def dfs(start, cur_t, min_t):
        for i in range(len(cost[start])):
            if cost[start][i] <= 100 and (i not in visit) and (cur_t + cost[start][i] <= min_t):
                if i == end:
                    min_t = cur_t + cost[start][i]
                    continue
                visit.add(i)
                min_t = dfs(i, cur_t + cost[start][i], min_t)
                visit.remove(i)
        return min_t

    min_time = 100 * n
    visit = {0}
    print(dfs(0, 0, min_time))

第二题

  • 01背包
  • 通过
def second():
    n, x = map(int, input().strip().split(' '))
    cost = []
    for _ in range(n):
        cost.append(list(map(int, input().strip().split(' '))))
    dp = [[0] * (x + 1) for _ in range(n)]
    for i in range(cost[0][1], x + 1):
        dp[0][i] = cost[0][0]

    for i in range(1, n):
        for j in range(x + 1):
            if cost[i][1] <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i][1]] + cost[i][0])
            else:
                dp[i][j] = dp[i - 1][j]
    print(dp[-1][-1])

第三题

def third():
    s = input()
    k = int(input())

    if k == 0:
        print(s)
    else:
        s += '0'
        res = []

        for c in s:
            while res and res[-1] > c:
                if k == 0:
                    break
                res.pop()
                k -= 1
            res.append(c)

        for i in range(len(res)):
            if res[i] != '0':
                print(''.join(res[i:-1]))
                break
        else:
            print('0')



全部评论

(2) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐