Решить программу на питоне

Question

Одному таксисту приснился красочный сон. Во сне он живет и работает в некотором городе, где абсолютно все улицы с односторонним движением. Эти улицы устроены так, что невозможно проехать с какого-либо перекрестка так, чтобы вернуться обратно на этот же перекресток, то есть в дорожной сети города нет циклов. 
Таким образом, если с перекрестка А можно попасть по направлению движения улиц на перекресток В, то люди вызывают такси, иначе их везет специальный муниципальный подземный транспорт за бесплатно. 
В связи с такими странными на наш взгляд правилами, таксистам в этом городе разрешено законом везти пассажира по любому маршруту, не нарушающему направления движения. Все в этом городе привыкли к такой ситуации и абсолютно спокойно относятся к тому, что таксисты везут их самым длинным путем. Само собой, заработок таксиста за одну поездку прямо пропорционален длине поездки, для упрощения будем считать, что стоимость одного километра поездки составляет ровно один рубль. 
Схема дорог города задана. Перекрестки города пронумерованы числами от 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.

Murad Mrd · Answer

лень

Иван Туманов · Answer

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)

GGG · Answer

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

Рустам Абдрашитов · Answer

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