算法题:Good Taxi Driver"/>
算法题: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()
测试案例
2 4 4 3 0 1 1 70 0 2 0 70 1 3 0 70 2 3 0 40 6 15 1 0 1 25 68 0 2 30 50 0 5 0 101 1 2 70 77 1 3 35 42 2 0 0 22 2 1 40 86 2 3 0 23 2 4 45 40 3 1 64 14 3 5 0 23 4 1 95 8 5 1 0 84 5 2 90 64 5 3 36 40
运行结果
更多推荐
算法题:Good Taxi Driver
发布评论