首页 > 滴滴 9.13 笔试 Python 算法岗
头像
lih627
编辑于 2020-09-13 21:43
+ 关注

滴滴 9.13 笔试 Python 算法岗

第一题

图的最小生成树

D 星群岛由 n 个小岛组成。为了加强小岛居民之间的交流,头目决定启动一个造桥工程,将全部 n 个岛连接到一起。

由于受到金融危机的影响,头目要求造桥的总成本要最少,并且还规定每一座桥的成本都不能超过 k 万 D 星币。

需要注意的是,由于受到地理环境和气候影响,有些小岛之间没有办法直接造桥。

现在给你 m 条小岛之间的造桥成本数据以及 k 的值,请问这个宏伟的造桥工程是否能够顺利完成?

注意:可能边不够,也可能费用超支。

输入描述
多组输入,第 1 行输入一个正整数 T 表示输入数据的组数。

对于每一组输入数据:输入 m+1 行。

第 1 行包含三个正整数,分别表示 n、m 和 k,n≤100,m≤1000,k≤10000,三个数字之间用空格隔开。

接下来 m 行表示 m 条小岛之间的造桥成本数据,每一行包含三个正整数,分别表示两个小岛的编号(从 1 开始)和这两个小岛之间的造桥成本(单位:万)。

输出描述
针对每一组输入数据,如果能够完成造桥工程输出 “Yes”,否则输出 “No”。

样例输入
2
3 3 400
1 2 200
1 3 300
2 3 500
3 3 400
1 2 500
1 3 600
2 3 700
样例输出
Yes
No

代码

class DSU:
    def __init__(self, n):
        self.parents = list(range(n + 1))

    def find(self, x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def un(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        self.parents[ry] = rx

    def isC(self, x, y):
        return self.find(x) == self.find(y)


def solve(n, k, graph):
    graph.sort(key=lambda x: x[2])
    dsu = DSU(n)
    cnt = 0
    for edge in graph:
        # print('edge', edge)
        x, y, cost = edge
        if dsu.isC(x, y):
            continue
        if cost > k:
            break
        dsu.un(x, y)
        cnt += 1
        if cnt == n - 1:
            break
    # print(dsu.parents)
    print('Yes' if cnt == n - 1 else 'No')


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        n, m, k = map(int, input().split())
        graph = []
        for __ in range(m):
            edge = list(map(int, input().split()))
            graph.append(edge)
        solve(n, k, graph)

第二题

最短路。注意时间转换

小滴正在筹划他的毕业旅行。他打算去找他的外国网友们,
首先第一站是法国巴黎,但是去巴黎的路线有很多,交通工具也有很多可供选择。
现在有一个结点数为 n,边的条数为 m 的无向图表示小滴到巴黎的所有路线。
其中小滴的家为结点 s,巴黎为结点 e,小滴出发时间为 start,请问小滴最早什么时候能到达巴黎?

单组输入,数字间有空格隔开。
第一行两个整数:结点数 n,边数 m(n<=1000,m<=10000)。
第二行到第 m+1 行每行各有三个整数:结点 u,结点 v,需要的时间 time(1<=u,v<=n,time<50,time 以小时为单位)。
最后一行为家的位置:s,巴黎的位置:e,出发时间 start
(1<=s,e<=n,出发时间格式为 month.day/hour,小时为 24 小时制,
出发年份默认为 2020 年,且一定会在 2020 年到达,数据保证有解。)

样例输入
4 4
1 2 5
1 3 6
2 4 8
3 4 6
1 4 7.9/8
样例输出
7.9/20

代码

import collections
import heapq

months = {1: 31, 2: 29, 3: 31, 4: 30, 5: 31,
          6: 30, 7: 31, 8: 31, 9: 30, 10: 31,
          11: 30, 12: 31}


def dijkstra(graph, s, e):
    heap = [[0, s]]
    dist = {}
    while heap and e not in dist:
        d, node = heapq.heappop(heap)
        if node in dist:
            continue
        dist[node] = d
        for nei, _d in graph[node]:
            if nei not in dist:
                heapq.heappush(heap, [d + _d, nei])
    return dist[e]


def solve(graph, s, e, month, day, hour):
    delta_hours = dijkstra(graph, s, e)
    # print('used {} hours'.format(delta_hours))
    delta_day = delta_hours // 24
    delta_hours -= delta_day * 24
    hour += delta_hours
    if hour >= 24:
        delta_day += 1
        hour -= 24
    day += delta_day
    while day > months[month]:
        day -= months[month]
        month += 1
        # day -= months[month]
    print("{}.{}/{}".format(month, day, hour))


if __name__ == '__main__':
    n, m = map(int, input().split())
    graph = collections.defaultdict(list)
    for _ in range(m):
        u, v, time = map(int, input().split())
        graph[u].append([v, time])
        graph[v].append([u, time])
    infos = input().split()
    s, e = map(int, infos[:2])
    md, hour = infos[2].split('/')
    hour = int(hour)
    month, day = map(int, md.split('.'))
    solve(graph, s, e, month, day, hour)

全部评论

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

推荐话题

相关热帖

近期热帖

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

近期精华帖

热门推荐