滴滴 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) #笔试题目##滴滴#
投递美团等公司10个岗位 >