Решить программу на питоне
Одному таксисту приснился красочный сон. Во сне он живет и работает в некотором городе, где абсолютно все улицы с односторонним движением. Эти улицы устроены так, что невозможно проехать с какого-либо перекрестка так, чтобы вернуться обратно на этот же перекресток, то есть в дорожной сети города нет циклов.
Таким образом, если с перекрестка А можно попасть по направлению движения улиц на перекресток В, то люди вызывают такси, иначе их везет специальный муниципальный подземный транспорт за бесплатно.
В связи с такими странными на наш взгляд правилами, таксистам в этом городе разрешено законом везти пассажира по любому маршруту, не нарушающему направления движения. Все в этом городе привыкли к такой ситуации и абсолютно спокойно относятся к тому, что таксисты везут их самым длинным путем. Само собой, заработок таксиста за одну поездку прямо пропорционален длине поездки, для упрощения будем считать, что стоимость одного километра поездки составляет ровно один рубль.
Схема дорог города задана. Перекрестки города пронумерованы числами от 1 до п. Наш таксист в своем сне находится на перекрестке номер S. Напишите программу, которая подскажет ему, сколько он максимально сможет заработать, когда ему придет заказ от клиента. Так как он не знает куда попросит его везти клиент, нужно для каждого перекрестка от 1 до и указать максимальную стоимость добраться до этого перекрестка из пункта S на такси.
Если по правилам на такси добраться из пункта S до какого-то перекрестка нельзя, вывести -1.
Формат ввода
Дорожная сеть задана следующим образом: в первой строке находятся два числа через пробел и и т — число перекрестков и число улиц в городе. 2 ≤ n, m ≤ 2 * 70.
В следующих т строках задана очередная односторонняя улица в виде трех чисел 4, В. d через пробел, где А начало улицы, В — конец улицы и d — ей длина. 1 ≤ A, B ≤n, 7 ≤ d ≤ 10.
Гарантируется, что в этой дорожной сети нет циклов. Некоторые пары перекрестков могут быть соединены двумя и более односторонними улицами. Дорожная сеть может быть не плоской за счет мостов и тоннелей.
В последней строке ввода содержится номер стартового перекрестка S. 1 ≤ S ≤n.
Формат вывода
Вывести и чисел в одну строку через пробел. і-е число обозначает длину самого длинного пути с перекрестка номер S до перекрестка номер і. Если до перекрестка номер і от S нельзя
доехать, не нарушая правила движения, вывести -1.
def max_distance(n, m, edges, S):
from collections import defaultdict
graph = defaultdict(list)
for A, B, d in edges:
graph[A].append((B, d))
max_distances = [-1] * (n + 1)
max_distances[S] = 0
def dfs(node):
if max_distances[node] != -1:
return max_distances[node]
max_distance_from_node = 0
for neighbor, distance in graph[node]:
max_distance_from_node = max(max_distance_from_node, dfs(neighbor) + distance)
max_distances[node] = max_distance_from_node
return max_distances[node]
for i in range(1, n + 1):
if i != S:
dfs(i)
return max_distances[1:]
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
S = int(input())
result = max_distance(n, m, edges, S)
print(' '.join(map(str, result))) import sys
import threading
def main():
import sys
import threading
sys.setrecursionlimit(1 << 25)
n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
A, B, d = map(int, sys.stdin.readline().split())
graph[A].append((B, d))
S = int(sys.stdin.readline())
visited = [False] * (n + 1)
stack = []
def dfs(u):
visited[u] = True
for v, w in graph[u]:
if not visited[v]:
dfs(v)
stack.append(u)
for u in range(1, n + 1):
if not visited[u]:
dfs(u)
dist = [float('-inf')] * (n + 1)
dist[S] = 0
while stack:
u = stack.pop()
if dist[u] != float('-inf'):
for v, w in graph[u]:
if dist[v] < dist[u] + w:
dist[v] = dist[u] + w
result = []
for i in range(1, n + 1):
if dist[i] == float('-inf'):
result.append('-1')
else:
result.append(str(dist[i]))
print(' '.join(result))
if __name__ == "__main__":
threading.Thread(target=main).start()
def find_longest_paths(n, m, roads, s):
adjacency_list = [[] for _ in range(n + 1)]
for a, b, d in roads:
adjacency_list[a].append((b, d))
max_costs = [-1] * (n + 1)
max_costs[s] = 0
visited = set()
queue = [(0, s)]
while queue:
current_cost, current_node = queue.pop(0)
if current_node in visited:
continue
visited.add(current_node)
for neighbor, distance in adjacency_list[current_node]:
new_cost = current_cost + distance
if max_costs[neighbor] < new_cost:
max_costs[neighbor] = new_cost
queue.append((new_cost, neighbor))
return max_costs[1:]
n, m = map(int, input().split())
roads = []
for _ in range(m):
a, b, d = map(int, input().split())
roads.append((a, b, d))
s = int(input())
max_costs = find_longest_paths(n, m, roads, s)
print(*max_costs)
лень