滴滴 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)