Alle Herausforderungen
Mittel 1 gelöst 100.0% Erfolgsquote

Shortest Weighted Routes

Find the minimum total route cost from city 1 to each city.

Das lernst du

  • Kürzeste Wege mit dem Dijkstra-Algorithmus finden
  • Mit einer Prioritätswarteschlange die nächste Stadt wählen
  • Veraltete Einträge in der Warteschlange überspringen

Problem

Find the minimum total route cost from city 1 to each city. Routes are directed: [u, v, cost] allows travel from u to v, not automatically back. You may use several routes. City 1 costs 0 to reach. Every city is reachable from city 1.

Implement shortest_weighted_routes(cities, routes).

Input

cities: Number of cities, numbered from 1.

routes: Directed routes [from_city, to_city, cost].

Output

Return the minimum costs in city order, starting with city 1.

Einschränkungen

1 ≤ cities ≤ 100,000. 0…200,000 routes; endpoints are 1…cities. Costs are integers from 1 to 1,000,000,000. Parallel routes and self-loops are allowed. Distances fit signed 64-bit.

Beispiele

Beispiel 1
Eingabe:
cities = 3
routes = [
    [1, 2, 5],
    [1, 3, 1],
    [3, 2, 2]
]

Erwartete Ausgabe:
expected = [0, 3, 1]
Eingabe:
long long cities = 3;
std::vector<std::vector<long long>> routes = {
    {1, 2, 5},
    {1, 3, 1},
    {3, 2, 2}
};

Erwartete Ausgabe:
std::vector<long long> expected = {0, 3, 1};
Eingabe:
long cities = 3;
long[][] routes = new long[][] {
    new long[] {1, 2, 5},
    new long[] {1, 3, 1},
    new long[] {3, 2, 2}
};

Erwartete Ausgabe:
long[] expected = new long[] {0, 3, 1};

Erläuterung

City 3 costs 1. Going from 1 through 3 to 2 costs 1 + 2 = 3, cheaper than the direct cost of 5.

Beispiel 2
Eingabe:
cities = 1
routes = []

Erwartete Ausgabe:
expected = [0]
Eingabe:
long long cities = 1;
std::vector<std::vector<long long>> routes = {};

Erwartete Ausgabe:
std::vector<long long> expected = {0};
Eingabe:
long cities = 1;
long[][] routes = new long[][] {};

Erwartete Ausgabe:
long[] expected = new long[] {0};

Erläuterung

The only city is the starting city. No travel is needed, so its distance is 0.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Alle Routen kosten positiv, also erweitere immer als Nächstes die aktuell günstigste noch nicht erreichte Stadt.

Hinweis 2

Baue gerichtete Adjazenzlisten und nutze eine Priority Queue, um ausgehende Routen wiederholt zu relaxen.

Hinweis 3

Parallele Routen und Self-Loops sind okay; aktualisiere nur, wenn ein neu gefundener Pfad günstiger ist.

Erwartete Komplexität

Zeit O((cities + routes) log cities), zusätzlicher Speicher O(cities + routes)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 695 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.