Distance la plus courte après les requêtes d'ajout de route I

3243. Distance la plus courte après les requêtes d'ajout de route I

Difficulté :Moyen

Sujets : Tableau, recherche en largeur d'abord, graphique

Vous recevez des requêtes sur un n entier et un tableau d'entiers 2D.

Il y a n villes numérotées de 0 à n - 1. Initialement, il existe une route unidirectionnelle de la ville i à la ville i 1 pour tous 0

queries[i] = [u_i, v_i] représente l'ajout d'une nouvelle route unidirectionnelle depuis la ville u_i à la ville v_i. Après chaque requête, vous devez trouver la longueur du chemin le plus court de la ville 0 à la ville n - 1.

Renvoyer une réponse de tableau où pour chaque i dans la plage [0, queries.length - 1], la réponse[i] est la longueur du chemin le plus court de la ville 0 à la ville n - 1 après avoir traité le premieri 1 requêtes.

Exemple 1 :

• Entrée : n = 5, requêtes = [[2,4],[0,2],[0,4]]
• Sortie : [3,2,1]
• Explication : Après avoir ajouté la route de 2 à 4, la longueur du chemin le plus court de 0 à 4 est 3. Après addition de la route de 0 à 2, la longueur du chemin le plus court de 0 à 4 est 2. Après l'ajout de la route de 0 à 4, la longueur du chemin le plus court de 0 à 4 est 1.

Exemple 2 :

• Entrée : n = 4, requêtes = [[0,3],[0,2]]
• Sortie : [1,1]
• Explication : Après addition de la route de 0 à 3, la longueur du chemin le plus court de 0 à 3 est 1. Après l'ajout de la route de 0 à 2, la longueur du chemin le plus court reste 1.

Contraintes :

• 3
• 1
• requêtes[i].length == 2
• 0
• 1
• Il n'y a pas de routes répétées parmi les requêtes.

Indice :

1. Maintenez le graphique et utilisez un algorithme de chemin le plus court efficace après chaque mise à jour.
2. Nous utilisons BFS/Dijkstra pour chaque requête.

Solution :

Nous devons simuler l'ajout de routes entre les villes et calculer le chemin le plus court de la ville 0 à la ville n - 1 après chaque ajout de route. Compte tenu des contraintes et de la nature du problème, nous pouvons utiliser la Breadth-First Search (BFS) pour les graphiques non pondérés.

Approche:

1. Représentation graphique :

   • Nous pouvons représenter les villes et les routes à l'aide d'une liste de contiguïté. Initialement, chaque ville i aura une route vers la ville i 1 pour tous 0
   • Après chaque requête, nous ajoutons la route de u_i à v_i dans le graphique.

2. Calcul du chemin le plus court (BFS) :

   • Nous pouvons utiliser BFS pour calculer le chemin le plus court de la ville 0 à la ville n - 1. BFS fonctionne bien ici car toutes les routes ont le même poids (chaque route a une longueur de 1).

3. Itération sur les requêtes :

   • Pour chaque requête, nous ajouterons la nouvelle route au graphique, puis utiliserons BFS pour trouver le chemin le plus court de la ville 0 à la ville n - 1. Après avoir traité chaque requête, nous stockons le résultat dans le tableau de sortie.

4. Efficacité :

   • Puisque nous utilisons BFS après chaque requête et que la taille du graphique peut être d'au plus 500 villes avec jusqu'à 500 requêtes, la complexité temporelle pour chaque BFS est O(n m), où n est le nombre de villes et m est le nombre de routes. Nous devons exécuter BFS jusqu'à 500 fois pour que la solution fonctionne efficacement dans les limites du problème.

Implémentons cette solution en PHP : 3243. Distance la plus courte après les requêtes d'ajout de route I

<?php /**
 * @param Integer $n
 * @param Integer[][] $queries
 * @return Integer[]
 */
function shortestDistanceAfterQueries($n, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to find the shortest path using BFS
 *
 * @param $graph
 * @param $n
 * @return int
 */
function bfs($graph, $n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$n = 5;
$queries = [[2, 4], [0, 2], [0, 4]];
print_r(shortestDistanceAfterQueries($n, $queries));

// Example 2
$n = 4;
$queries = [[0, 3], [0, 2]];
print_r(shortestDistanceAfterQueries($n, $queries));
?>

Explication:

1. Initialisation du graphique :

   • Un graphique de liste de contiguïté est utilisé pour représenter les villes et les routes.
   • Au départ, les routes n'existent qu'entre des villes consécutives (i à i 1).

2. Fonction BFS :

   • BFS est utilisé pour calculer la distance la plus courte entre la ville 0 et la ville n - 1. Nous maintenons une file d'attente pour BFS et un tableau de distances pour stocker le nombre minimum de routes (bords) pour atteindre chaque ville.
   • Initialement, la distance jusqu'à la ville 0 est définie sur 0, et toutes les autres villes ont une distance infinie (PHP_INT_MAX).
   • Au fur et à mesure que nous traitons chaque ville dans la file d'attente BFS, nous mettons à jour les distances de ses villes voisines et continuons jusqu'à ce que toutes les villes accessibles soient visitées.

3. Traitement des requêtes :

   • Pour chaque requête, la nouvelle route est ajoutée au graphique (u -> v).
   • BFS est appelé pour calculer le chemin le plus court de la ville 0 à la ville n-1 après la mise à jour.
   • Le résultat de BFS est stocké dans le tableau de résultats.

4. Sortie :

   • Le tableau de résultats contient les chemins les plus courts après chaque requête.

5. Complexité temporelle :

   • Chaque BFS prend O(n m), où n est le nombre de villes et m est le nombre de routes. Puisque le nombre de requêtes est q, la complexité temporelle globale est O(q * (n m)), ce qui devrait être efficace pour les contraintes données.

Exemple de procédure pas à pas :

Pour l'entrée n = 5 et les requêtes = [[2, 4], [0, 2], [0, 4]] :

• Au départ, les routes sont [0 -> 1 -> 2 -> 3 -> 4].
• Après la première requête [2, 4], les routes sont [0 -> 1 -> 2 -> 3 -> 4] et le chemin le plus court de 0 à 4 est 3 (en utilisant le chemin 0 -> 1 -> 2 -> 4).
• Après la deuxième requête [0, 2], les routes sont [0 -> 2, 1 -> 2 -> 3 -> 4], et le chemin le plus court de 0 à 4 est 2 (en utilisant le chemin 0 -> 2 -> 4).
• Après la troisième requête [0, 4], les routes sont [0 -> 2, 1 -> 2 -> 3 -> 4], et le chemin le plus court de 0 à 4 est 1 (route directe 0 -> 4).

Ainsi, la sortie est [3, 2, 1].

Réflexions finales :

• La solution utilise BFS pour chaque requête afin de calculer efficacement le chemin le plus court.
• Le graphique est mis à jour dynamiquement à mesure que de nouvelles routes sont ajoutées à chaque requête.
• La solution fonctionne bien dans les contraintes du problème et traite efficacement jusqu'à 500 requêtes avec jusqu'à 500 villes.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!