算法题：Good Taxi Driver

编程入门行业动态更新时间:2024-10-26 08:30:22

算法题：Good Taxi Driver

题目描述

测试用例

考察知识点

图求解最短路径

本次实现采用迪杰斯特拉算法和深度优先遍历进行实现

Python实现(迪杰斯特拉算法)


def goodTaxiDriver():case_n = int(sys.stdin.readline().strip())for case_i in range(case_n):n, m, target_ind = map(int, sys.stdin.readline().strip().split())graph = [[(float("inf"), float("inf")) for _ in range(n)] for _ in range(n)]for _ in range(m):s, e, v, l = map(int, sys.stdin.readline().strip().split())graph[s][e] = (v, l)visited = [False for _ in range(n)]# 存放从开始节点到当前节点(父亲节点, 最短时间，上一次使用速度)dist = [(-1, float("inf"), -1) for _ in range(n)]parent = [-1 for _ in range(n)]v = 70# 更新从开始节点到其他节点最短路径for i in range(1, n):if graph[0][i][0] != float("inf"):cur_v = graph[0][i][0]if cur_v == 0:cur_v = velif cur_v > v:cur_v = vtime = graph[0][i][1] / cur_vdist[i] = (0, time, cur_v)visited[0] = Truefor i in range(n):middle = -1min_dst = float("inf")cur_v = -1for i in range(n):if not visited[i] and dist[i][1] < min_dst:min_dst = dist[i][1]middle = ivisited[middle] = Trueparent[middle] = dist[middle][0]cur_v = dist[middle][2]# 更新新加入节点到其他节点最短路径for i in range(n):if not visited[i] and graph[middle][i][0] != float("inf"):t_v = graph[middle][i][0]if t_v == 0:t_v = dist[middle][2]elif t_v > dist[middle][2]:t_v = dist[middle][2]c_time = graph[middle][i][1] / t_vtotal_time = c_time + dist[middle][1]if total_time < dist[i][1]:dist[i] = (middle, total_time, t_v)# 回溯求解最短路径ret = ""t = target_indwhile t != -1:ret = str(t) + " " + rett = parent[t]print("#{} {}".format(case_i+1, ret))goodTaxiDriver()

Python实现(深度优先遍历算法)

# coding:utf-8"""
2
4 4 3
0 1 1 70
0 2 0 70
1 3 0 70
2 3 0 40
"""
import sys
def good_taxi_driver():def compute_time(path, v):# 计算每个路径耗费时间c_time = 0for i in range(len(path)-1):s, e = path[i], path[i+1]cur_v, cur_l = graph[s][e]if cur_v == 0:cur_v = velif cur_v > v:cur_v = vc_time += cur_l / cur_vv = cur_vreturn c_timedef dfs(x, res, t, dst_ind, v):"""利用深度优先遍历查找目标路径x: 节点索引res: 存放最终结果list，[list, int]t: 存放路径dst_ind: 存放结束节点路径"""if x == dst_ind:c_time = compute_time(t, v)if len(res) == 0:res.append(t.copy())res.append(c_time)else:if res[-1] > c_time:res.clear()res.append(t.copy())res.append(c_time)else:for i in range(n):if not visited[i] and graph[x][i][0] != float("inf"):visited[i] = Truet.append(i)dfs(i, res, t, dst_ind, v)t.pop()visited[i] = Falsecase_n = int(sys.stdin.readline().strip())for case_i in range(case_n):# 车开始速度speed = 70n, m, target_ind = map(int, sys.stdin.readline().strip().split())graph = [[(float("inf"), float("inf")) for _ in range(n)] for _ in range(n)]for _ in range(m):s, e, v, l = map(int, sys.stdin.readline().strip().split())graph[s][e] = (v, l)visited = [False for _ in range(n)]res = []t = [0]dfs(0, res, t, target_ind, speed)optimal_path = " ".join(list(map(str, res[0])))print("#{} {}".format(case_i, optimal_path))good_taxi_driver()

测试案例