Comments

• 
  

  0

  dashleb  March 12, 2025, 3:10 a.m.

  import heapq

  def minimal_fuel_cost():

  # Чтение входных данных
  N = int(input())  # Количество городов
  graph = {i: [] for i in range(1, N + 1)}  # Словарь для хранения графа
  
  # Заполнение графа
  for _ in range(N):
      city1, city2, distance, fuel_per_km = map(int, input().split())
      cost = distance * fuel_per_km  # Вычисляем стоимость проезда
      graph[city1].append((city2, cost))
      graph[city2].append((city1, cost))  # Если дороги двунаправленные
  
  # Алгоритм Дейкстры
  start_city = 1
  end_city = N
  distances = {city: float('inf') for city in graph}
  distances[start_city] = 0
  priority_queue = [(0, start_city)]  # Очередь с приоритетом (расстояние, город)
  
  while priority_queue:
      current_cost, current_city = heapq.heappop(priority_queue)
  
      # Если текущая стоимость больше уже найденной, пропускаем
      if current_cost > distances[current_city]:
          continue
  
      # Обновляем расстояния до соседних городов
      for neighbor, cost in graph[current_city]:
          new_cost = current_cost + cost
          if new_cost < distances[neighbor]:
              distances[neighbor] = new_cost
              heapq.heappush(priority_queue, (new_cost, neighbor))
  
  # Выводим минимальные затраты
  print(distances[end_city])

  Пример использования

  if __name__ == "__main__": minimal_fuel_cost()