Shortest Weighted Routes

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

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};

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};

Referenzen

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

• CSES: Shortest Routes I