Tous les défis
Moyen 1 résolu 100.0 % de réussite

Shortest Weighted Routes

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

Ce que vous allez apprendre

  • Trouver les plus courts chemins avec Dijkstra
  • Utiliser une file de priorité pour choisir la ville suivante
  • Ignorer les entrées obsolètes de la file

Problème

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.

Contraintes

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.

Exemples

Exemple 1
Entrée :
cities = 3
routes = [
    [1, 2, 5],
    [1, 3, 1],
    [3, 2, 2]
]

Sortie attendue :
expected = [0, 3, 1]
Entrée :
long long cities = 3;
std::vector<std::vector<long long>> routes = {
    {1, 2, 5},
    {1, 3, 1},
    {3, 2, 2}
};

Sortie attendue :
std::vector<long long> expected = {0, 3, 1};
Entrée :
long cities = 3;
long[][] routes = new long[][] {
    new long[] {1, 2, 5},
    new long[] {1, 3, 1},
    new long[] {3, 2, 2}
};

Sortie attendue :
long[] expected = new long[] {0, 3, 1};

Explication

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

Exemple 2
Entrée :
cities = 1
routes = []

Sortie attendue :
expected = [0]
Entrée :
long long cities = 1;
std::vector<std::vector<long long>> routes = {};

Sortie attendue :
std::vector<long long> expected = {0};
Entrée :
long cities = 1;
long[][] routes = new long[][] {};

Sortie attendue :
long[] expected = new long[] {0};

Explication

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

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Tous les coûts de route sont positifs, donc développez toujours la ville non atteinte la moins chère.

Indice 2

Construisez des listes d’adjacence orientées et utilisez une file de priorité pour détendre à répétition les routes sortantes.

Indice 3

Les routes parallèles et les boucles sur soi-même sont acceptées ; mettez à jour seulement si un nouveau chemin est moins cher.

Complexité attendue

temps O((cities + routes) log cities), espace supplémentaire O(cities + routes)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 695 ms - 5/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.