Je n'arrive pas à passer en temps cet exercice de France IOI
Placer des caméras pour surveiller le parcours ne suffit pas, et la société de Julie doit placer un certain nombre d'agents de sécurité. Ils sont prêts à intervenir au moindre problème détecté par Jacques, le chef de la sécurité, sur ses écrans de surveillance. Grâce aux caméras, Jacques est capable de connaître l'intersection la plus proche du problème. Il sait également à tout moment à quel endroit sont placés ses agents, et peut ainsi choisir quel, ou quels agents peuvent se rendre le plus rapidement sur place.
Julie ne veut pas qu'une éventuelle panne d'ordinateur remette en cause la sécurité des évènements, et vous demande donc d'écrire un programme qui génère un tableau, indiquant les distances entre toutes les intersections du parcours. Muni de ce tableau, Jacques pourra ainsi très rapidement déterminer à quelle distance se trouve chaque agent du problème, et prendre la bonne décision.
Vous devez écrire un programme qui affiche une ligne par intersection, dans l'ordre des numéros d'intersections, avec sur cette ligne, la distance de l'intersection à chacune des autres intersections, également dans l'ordre de leur numéro.
Limites de temps et de mémoire (Python)
Temps : 10 s sur une machine à 1 GHz.
Mémoire : 8 000 ko.
Contraintes
2 <= N <= 500, où N est le nombre d'intersections du labyrinthe.
1 <=K <= N, où K est le numéro d'une intersection.
1 <= A <= 5000, où A est le nombre de sentiers du labyrinthe.
1 <= L <= 1000, où L est la longueur d'un sentier.
Entrée
La première ligne de l'entrée contient deux entiers séparés par une espace, N et A, respectivement le nombre d'intersections, et de sentiers du labyrinthe.
Chacune des A lignes suivantes contient trois entiers, séparés par des espaces. Les deux premiers entiers sont les numéros des deux intersections reliées par le sentier. Le troisième représente la longueur du sentier.
Sortie
Vous devez écrire N lignes sur la sortie, contenant chacune N entiers, séparés par des espaces. Le jème nombre de la ième colonne représente la distance du plus court chemin entre la ième et la jème intersection.
voici mon code avec l'algorithme de Floyd-Warshall
import sys
def floyd_warshall(n, graph):
# Initialisation de la matrice des distances
dist = [[float('inf')] * n for _ in range(n)]
# Distance de chaque intersection à elle-même est 0
for i in range(n):
dist[i][i] = 0
# Remplir la matrice avec les distances directes du graphe
for (u, v, w) in graph:
dist[u-1][v-1] = w
dist[v-1][u-1] = w
# Algorithme de Floyd-Warshall
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
def main():
# Lecture de l'entrée
# n, a = map(int, input().split())
n, a = map(int, sys.stdin.readline().split())
graph = []
for _ in range(a):
u, v, l = map(int, input().split())
graph.append((u, v, l))
# Appel de la fonction pour obtenir la matrice des plus courts chemins
distances = floyd_warshall(n, graph)
# Affichage de la matrice des distances
for i in range(n):
# print(" ".join(map(str, distances[i])))
sys.stdout.write(" ".join(map(str, distances[i])) + "\n")
main()
et en sortie des tests
Test 1
Succès
Exécuté en 0,06 seconde.
100 %
Test 2
Succès
Exécuté en 0,06 seconde.
100 %
Test 3
Succès
Exécuté en 0,07 seconde.
100 %
Test 4
Succès
Exécuté en 0,16 seconde.
100 %
Test 5
Succès
Exécuté en 0,75 seconde.
100 %
Test 6
Succès
Exécuté en 5,17 secondes.
100 %
Test 7
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
0 %
Test 8
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
0 %
Test 9
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
0 %
Test 10
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
Ce qui est invariant par rapport à j pourrait être placé avant la boucle dans une autre variable.
dist_ik = dist[i][k] dist_k = dist[k] # C'est une ligne (dans la boucle sur k_). dist_i = dist[i] # Une autre ligne(boucle sur i). dist[i][j] pourrait être remplacé par: dist_i[j]
Si dist[i][k] est infini, il est inutile de faire la boucle sur j car rien ne sera plus grand.
Je ne sais pas si l'utilisation de "array" pourrait accélérer?
Je ne comprend pas pourquoi tu ne génères pas directement la mattrice à partir des données. Tu connais la dimension de ta matrice dès la première ligne (N, A).
Je ne sais pas non plus pourquoi France IOI vous oblige à utiliser sys.stdout.write avec une chaîne. print(*distance[i]) serait plus rapide.
Quand tu passes une matrice en paramètre à une fonction, tu n'as pas besoin de la retourner. Petit exemple bête qui marche: def calcul(a): a[1][1] = 2 a = [[0] * 3 for _ in range(3)] calcul(a) print(a[1][1])
- Edité par PierrotLeFou 17 août 2024 à 4:34:15
Le Tout est souvent plus grand que la somme de ses parties.
Certaines personnes pourraient ne pas savoir quelle est la façon de tester leur programme. Si le résultat attendu donné dans les exemples est assez volumineux, ce n'est pas évident de vérifier à la main. J'explique comment je procède. Toute autre méthode équivalente fera l'affaire. D'abord, je fais un copier-coller des données d'entrée dans un fichier (ici "af.t"). Je fais de même pour les résultats de sortie (ici "ref.t"). Ensuite je rédige mon programme (ici "af.py"). En fonction du système d'exploitation, je pourrais faire: Windows sous cmd: > type af.txt | py af.py > out.txt > comp out.txt ref.txt Linux avec une console: $ cat af.t | py af.py > out.t $ diff -u out.t ref.t Dans les deux cas, si Python donne une erreur, on corrige son code. Si la comparaison n'est pas bonne (aucun message si c'est bon), on a un bug et on revoit son code. Voici mon code qui fonctionne avec l'exemple donné au début: (certains exercices donnent plus d'un exemple) - # Lecture des paramètre et initialisation du graphe. n, a = map(int, input().split()) graphe = [[float('inf')] * n for _ in range(n)] for i in range(n): graphe[i][i] = 0 # Lecture des sentiers et assignation dans le graphe. for _ in range(a): u, v, w = map(int, input().split()) graphe[u-1][v-1] = w graphe[v-1][u-1] = w # Algorithme de Floyd-Warshall. infini = float("inf") for k in range(n): graphe_k = graphe[k] for i in range(n): graphe_i = graphe[i] graphe_ik = graphe_i[k] if graphe_ik == infini: continue for j in range(n): graphe_ikj = graphe_ik + graphe_k[j] if graphe_i[j] > graphe_ikj: graphe_i[j] = graphe_ikj # Affichage des résultats. for i in range(n): print(*graphe[i])
Le Tout est souvent plus grand que la somme de ses parties.
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
0 %
Test 8
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
0 %
Test 9
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
0 %
Test 10
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
0 %
TOTAL
Échec
Vous avez réussi 6 tests sur 10.
60 %
Si je l’intègre à l'intérieur d'une fonction
le test 6 passe de 6.63s à 3.25s, et ton programme passe en plus le test 7
def main():
# Lecture des paramètre et initialisation du graphe.
n, a = map(int, input().split())
graphe = [[float('inf')] * n for _ in range(n)]
for i in range(n):
graphe[i][i] = 0
# Lecture des sentiers et assignation dans le graphe.
for _ in range(a):
u, v, w = map(int, input().split())
graphe[u-1][v-1] = w
graphe[v-1][u-1] = w
# Algorithme de Floyd-Warshall.
infini = float("inf")
for k in range(n):
graphe_k = graphe[k]
for i in range(n):
graphe_i = graphe[i]
graphe_ik = graphe_i[k]
if graphe_ik == infini: continue
for j in range(n):
graphe_ikj = graphe_ik + graphe_k[j]
if graphe_i[j] > graphe_ikj:
graphe_i[j] = graphe_ikj
# Affichage des résultats.
for i in range(n):
print(*graphe[i])
main()
Test 1
Succès
Exécuté en 0,06 seconde.
100 %
Test 2
Succès
Exécuté en 0,06 seconde.
100 %
Test 3
Succès
Exécuté en 0,07 seconde.
100 %
Test 4
Succès
Exécuté en 0,12 seconde.
100 %
Test 5
Succès
Exécuté en 0,44 seconde.
100 %
Test 6
Succès
Exécuté en 3,25 secondes.
100 %
Test 7
Succès
Exécuté en 6,57 secondes.
100 %
Test 8
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
0 %
Test 9
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
0 %
Test 10
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
Bha j'ai pas accès à l'exo. Je mets mon code ici au cas, à voir si c'est plus rapide dans une fonction:
from sys import stdin
n,a = map(int,input().split())
c = list()
t = [{i:0} for i in range(n)]
for l in stdin.read().splitlines():
i,j,l = map(int,l.split())
i,j = i-1,j-1
t[j][i] = t[i][j] = l
c.append((i,j))
for i,j in c:
for j2 in t[j]:
if not j2 in t[i]:
c.append((i,j2))
t[j2][i] = t[i][j2] = t[i][j] + t[j][j2]
else:
l = t[i][j] + t[j][j2]
if l<t[i][j2]:
t[j2][i] = t[i][j2] = l
for i in t:
print(*[y for x,y in sorted(i.items())])
Dans ce problème, on vous demande en fait de calculer les longueurs des plus courts chemins entre toutes les paires d'intersections possibles.
Il est bien sûr possible d'appliquer l'algorithme de plus court chemin Dijkstra vu précédemment pour chaque point de départ et de le laisser poursuivre à chaque fois jusqu'à-ce qu'un chemin ait été trouvé pour chaque destination.
L'algorithme Dijkstra a une complexité en temps de A*log(A), où A est le nombre d'arêtes du graphe (on peut aussi l'implémenter en N2, mais c'est moins intéressant ici. Si on l'applique pour chaque point de départ, on obtient un algorithme de complexité N*A*log(A), soit de l'ordre de 500*5000*13 opérations en pire cas, donc 32 500 000. Avec l'implémentation de Dijkstra en N2, on obtient une complexité totale de N3, soit de l'ordre de 5003 opérations, ou 125 000 000.
Dans le cas où l'on a un nombre important d'arcs par rapport au nombre de nœuds, il existe un algorithme très court qui permet de calculer tous les plus courts chemins et qui peut être plus rapide. Il s'agit de l'algorithme de Floyd-Warshall, dont la complexité est de N3. Le nombre d'itérations est plus important que pour N dijkstra (avec la première implémentation), mais son implémentation demande tellement peu d'instructions qu'il est plus rapide en pratique.
Cet algorithme nécessite de travailler avec la représentation par matrice d'adjacence et demande donc d'utiliser un tableau de N*N, dans lequel on stocke toutes les distances entre intersections. On initialise le tableau avec les distances fournies par les arcs pour les nœuds qui sont reliés directement, et avec une valeur "infinie" pour les autres. Pour les langages qui ne permettent pas de gérer des valeurs infinies, on se contentera de prendre la valeur maximale du type de données que l'on utilise.
Le principe de l'algorithme se base sur la relation suivante :
Le plus court chemin pour aller de source à dest est soit l'arc allant directement de source à dest, soit un chemin passant par un nœud intermédiaire inter. Le chemin du deuxième cas consiste alors en le plus court chemin de source à inter, suivi du plus court chemin de inter à dest.
Il s'agit d'une définition récursive, où pour déterminer le plus court chemin entre deux points, on essaie le chemin direct et les chemins passant par chaque nœud intermédiaire possible. On peut l'écrire directement en C++ :
int dist[MAX_NB_NOEUDS][MAX_NB_NOEUDS];
int PlusCourtChemin(int source, int dest)
{
int minDistance = dist[source][dest];
for (int inter = 0; inter < nbNoeuds; inter++)
if ((inter != source) && (inter != dest)
{
int curDistance = PlusCourtChemin(source, inter) + PlusCourtChemin(inter, dest);
minDistance = min(minDistance, curDistance);
}
return minDistance;
}
Si l'on se contente de l'écrire de cette manière, on tombe cependant dans une récursion infinie : pour calculer le plus court chemin de source à dest, on a besoin du plus court chemin entre source et inter, qui lui-même nécessite de connaître le plus court chemin de source à dest.
Pour éviter cette boucle infinie, il faut commencer par réécrire notre fonction récursive d'une autre manière, en lui passant 3 paramètres : le point de départ, le point d'arrivée et le plus grand index de point intermédiaire que l'on a le droit d'utiliser pour aller du départ à l'arrivée.
Le plus court chemin de source à dest n'utilisant que des points intermédiaires dont l'index ne dépasse pas inter correspond nécessairement à l'un des trois cas suivants :
on utilise l'arc reliant directement source à dest.
on passe par inter, en prenant le plus court chemin de source à inter puis le plus court chemin de inter à dest.
on ne passe pas par inter, donc on prend le plus court chemin de source à dest n'utilisant que des points intermédiaires dont l'index ne dépasse pas inter-1.
On a toujours une fonction récursive, mais comme le point intermédiaire décrémente à chaque appel imbriqué, on est maintenant certain de ne pas tomber dans une boucle infinie : la récursion s'arrête lorsque inter atteint 0. Pour éviter de tester pour chaque valeur de inter la possibilité consistant à prendre directement l'arête source-dest, on ne fait le test que lorsque inter a atteint la valeur 0, c'est à dire que l'on ne peut plus du tout prendre d'arc intermédiaire.
Pour calculer le plus court chemin entre deux points source et dest, on appelle donc la fonction suivante, avec nbNoeuds comme valeur pour inter.
int distance[MAX_NOEUDS][MAX_NOEUDS];
int PlusCourtChemin(int source, int dest, int inter)
{
if (inter == 0)
return distance[source][dest];
int distance1 = plusCourtChemin(source, inter, inter - 1) + plusCourtChemin(inter, dest, inter - 1);
int distance2 = plusCourtChemin(source, dest, inter - 1);
return min(distance1, distance2);
}
Cette fonction n'est plus infinie mais reste tout de même extrêmement lente : chaque appel à la fonction avec inter > 0, génère trois appels récursifs. Le nombre total d'appels à la fonction est donc de l'ordre de 3N, ce qui est énorme.
Notre fonction a trois paramètres, dont chacun peut prendre nbNoeuds valeurs possibles. Au total, il y a donc au maximum nbNoeuds3 manières possibles d'appeler la fonction. Lors des 3nbNoeuds appels décrits plus haut, une très grande partie correspond à des calculs déjà effectués. On peut donc éviter de les refaire, en stockant dans un tableau les résultats déjà calculés. On utilise un tableau à 3 dimensions, chaque dimension correspondant à un paramètre de la fonction. Le tableau contient la valeur -1 lorsque le calcul n'a jamais été fait. Il s'agit de ce que l'on appelle un algorithme dynamique.
int distance[MAX_NB_NOEUDS][MAX_NB_NOEUDS];
int dejaCalcule[MAX_NB_NOEUDS][MAX_NB_NOEUDS][MAX_NB_NOEUDS];
int plusCourtChemin(int source, int dest, int inter)
{
if (inter == 0)
return distance[source][dest];
if (dejaCalcule[source][dest][inter] != -1)
return dejaCalcule[source][dest][inter];
int distance1 = plusCourtChemin(source, inter, inter - 1) + plusCourtChemin(inter, dest, inter - 1);
int distance2 = plusCourtChemin(source, dest, inter - 1);
int distanceMin = min(distance1, distance2);
dejaCalcule[source][dest][inter] = distanceMin;
return distanceMin;
}
Cette version est beaucoup plus rapide que la précédente, mais a un gros inconvénient : elle utilise une grande quantité de mémoire : nbNoeuds3 entiers, soit près de 4Go pour 1000 nœuds.
Toute cette mémoire n'est cependant pas nécessaire, si l'on remarque que pour calculer les valeurs des cases dont la troisième coordonnée est inter, on a uniquement besoin de connaître les résultats correspondant à des cases dont la troisième coordonnée est inter - 1 : chacun des trois appels récursifs se fait avec cette valeur comme troisième paramètre.
En utilisant cette propriété, on peut ainsi commencer par calculer toutes les cases dont la troisième coordonnée est 0, puis toutes les cases dont la troisième coordonnée est 1, etc. A tout moment, on n'a alors besoin de garder en mémoire que les valeurs des cases pour la troisième coordonnée précédente, et celles de la valeur courante.
Pour profiter de cette propriété, il faut donc commencer par écrire la solution de manière itérative, pour que les calculs soient faits valeur de inter par valeur de inter :
for (int inter = 0; inter < nbNoeuds; inter++)
for (int dest = 0; dest < nbNoeuds; dest++)
for (int source = 0; source < nbNoeuds; source++)
{
if (inter == 0)
dejaCalcule[source][dest][0] = distance[source][inter] + distance[inter][dest];
else
{
int dist1 = dejaCalcule[source][dest][inter - 1];
int dist2 = dejaCalcule[source][inter][inter - 1] + dejaCalcule[inter][dest][inter - 1];
dejaCalcule[source][dest][inter] = min(dist1, dist2);
}
}
Comme on n'a maintenant besoin que des cases de deux valeurs différentes de inter à tout moment, on peut utiliser un modulo 2 et réduire la troisième dimension à deux valeurs :
int dejaCalcule[MAX_NB_NOEUDS][MAX_NB_NOEUDS][2];
for (int C = 0; C < nbNoeuds; C++)
for (int dest = 0; dest < nbNoeuds; dest++)
for (int source = 0; source < nbNoeuds; source++)
{
if (inter == 0)
dejaCalcule[source][dest][0] = distance[source][inter] + distance[inter][dest];
else
{
int dist1 = dejaCalcule[source][dest][(inter - 1) % 2];
int dist2 = dejaCalcule[source][inter][(inter - 1) % 2] +
dejaCalcule[C][dest][(inter - 1) % 2];
dejaCalcule[source][dest][inter % 2] = min(dist1, dist2);
}
}
On a alors un algorithme de complexité nbNoeuds3 en temps, et nbNoeuds2 en mémoire.
Cet algorithme peut cependant être encore simplifié, si l'on stocke dans la même case le résultat pour inter, et le résultat pour inter - 1. En effet, on peut remarquer que pour les mêmes valeurs de source et de dest, la valeur pour le paramètre inter est toujours inférieure ou égale à la valeur pour C - 1. Si au lieu de stocker la valeur pour le paramètre inter dans une case séparée, on se contente d'écraser la valeur pour inter - 1, la valeur peut changer et ne plus représenter ce qui correspond aux paramètres source, dest et inter - 1, mais c'est toujours une distance possible de chemin entre source et dest qui ne peut être que meilleure. En écrasant la valeur au lieu de stocker séparément, on ne change donc pas le résultat final de l'algorithme.
Ceci permet de travailler directement dans le tableau distance, qu'il est alors inutile de recopier au départ :
for (int inter = 0; inter < nbNoeuds; inter++)
for (int dest = 0; dest < nbNoeuds; dest++)
for (int source = 0; source < nbNoeuds; source++)
distance[source][dest] = min(distance[source][dest],
distance[source][inter] + distance[inter][dest]);
On n'a alors plus que trois boucles imbriquées, contenant une seule instruction. On obtient donc une manière très simple et très courte d'implémenter l'algorithme de Floyd-Warshall.
@josmiley
voici le résultat
Test 1
Échec
La réponse donnée par votre programme est incorrecte. Il a affiché :
effectivement, là ça devrait être bon, mais vu les extend je doute que ça passe niveau mémoire.
from sys import stdin
n,a = map(int,input().split())
c = list()
t = [{i:0} for i in range(n)]
for l in stdin.read().splitlines():
i,j,l = map(int,l.split())
i,j = i-1,j-1
t[j][i] = t[i][j] = l
c.extend(((i,j),(j,i)))
for i,j in c:
for j2 in t[j]:
if not j2 in t[i]:
c.extend(((i,j2),(j2,i)))
t[j2][i] = t[i][j2] = t[i][j] + t[j][j2]
else:
l = t[i][j] + t[j][j2]
if l<t[i][j2]:
t[j2][i] = t[i][j2] = l
for i in t:
print(*[y for x,y in sorted(i.items())])
j'ai mis ton code dans une fonction car ça va plus vite
from sys import stdin
def main():
n,a = map(int,input().split())
c = list()
t = [{i:0} for i in range(n)]
for l in stdin.read().splitlines():
i,j,l = map(int,l.split())
i,j = i-1,j-1
t[j][i] = t[i][j] = l
c.extend(((i,j),(j,i)))
for i,j in c:
for j2 in t[j]:
if not j2 in t[i]:
c.extend(((i,j2),(j2,i)))
t[j2][i] = t[i][j2] = t[i][j] + t[j][j2]
else:
l = t[i][j] + t[j][j2]
if l<t[i][j2]:
t[j2][i] = t[i][j2] = l
for i in t:
print(*[y for x,y in sorted(i.items())])
main()
explications de France IOI
L'interpréteur Python met beaucoup de temps à exécuter des instructions qui se trouvent en dehors de toute fonction. Dans le programme suivant :
def dedans(nbFois):
for numFois in range(nbFois):
print("Dedans")
nbFois = int(input())
for numFois in range(nbFois):
print("Dehors")
dedans(numFois)
les instructions en dehors de la fonction peuvent mettre plus de temps à s'exécuter que celles qui se trouvent à l'intérieur ! En effet, le programme qui exécute les scripts Python effectue beaucoup plus de traitements et de mise en contexte pour les instructions du corps global (nous vous décrirons peut-être lesquelles un de ces jours).
Pour remédier à cela, il suffit de mettre les instructions du corps global dans une fonction, que l'on nommera main pour se conformer aux langages exigeant une telle fonction (C, C++ et Java par exemple). On appellera donc cette fonction dans le corps global, et ce sera la seule instruction s'y trouvant :
def dedans(nbFois):
for numFois in range(nbFois):
print("Dedans")
def main():
nbFois = int(input())
for numFois in range(nbFois):
print("Dehors")
dedans(numFois)
main()
Cela peut nettement accélérer certains programmes et vous sera nécessaire dans certains exercices.
Bon après l'interpréteur Python sur France IOI date un peu beaucoup.
Voici le résultat
Test 1
Succès
Exécuté en 0,06 seconde.
100 %
Test 2
Succès
Exécuté en 0,06 seconde.
100 %
Test 3
Succès
Exécuté en 0,07 seconde.
100 %
Test 4
Succès
Exécuté en 0,17 seconde.
100 %
Test 5
Succès
Exécuté en 0,93 seconde.
100 %
Test 6
Succès
Exécuté en 6,87 secondes.
100 %
Test 7
Erreur
Votre programme a échoué à la suite d'un accès mémoire en dehors des zones réservées, ou d'un dépassement de la limite de mémoire.
0 %
Test 8
Erreur
Votre programme a échoué à la suite d'un accès mémoire en dehors des zones réservées, ou d'un dépassement de la limite de mémoire.
0 %
Test 9
Erreur
Votre programme a échoué à la suite d'un accès mémoire en dehors des zones réservées, ou d'un dépassement de la limite de mémoire.
0 %
Test 10
Erreur
Votre programme a échoué à la suite d'un accès mémoire en dehors des zones réservées, ou d'un dépassement de la limite de mémoire.
j'ai l'impression que vous calculez l'ensemble de la matrice, alors qu'il suffirait d'en calculer que la moitié vue qu'elle est symétrique selon la diagonale [i,i]
Elle est bien symétrique (vérifié par le programme lui-même), mais le calcul ne semble pas symétrique.
À suivre ...
edit:
Il semble que ça marche. C'est un peu moins optimisé, mais si on divise par deux le nombre de calculs, on devrait sauver beaucoup.
Et on ne fait pas de calcul pour la diagonale.
J'ai pris ma version sans fonction, mais la modification est facile. Voici mon nouveau code: - # Lecture des paramètre et initialisation du graphe. n, a = map(int, input().split()) graphe = [[float('inf')] * n for _ in range(n)] for i in range(n): graphe[i][i] = 0 # Lecture des sentiers et assignation dans le graphe. for _ in range(a): u, v, w = map(int, input().split()) graphe[u-1][v-1] = w graphe[v-1][u-1] = w # Algorithme de Floyd-Warshall. infini = float("inf") for k in range(n): graphe_k = graphe[k] for i in range(n): graphe_i = graphe[i] graphe_ik = graphe_i[k] if graphe_ik == infini: continue for j in range(i+1,n): graphe_ikj = graphe_ik + graphe_k[j] if graphe_i[j] > graphe_ikj: graphe_i[j] = graphe_ikj graphe[j][i] = graphe_ikj # Affichage des résultats. for i in range(n): print(*graphe[i]) """ for i in range(n): for j in range(i+1, n): if graphe[i][j] != graphe[j][i]: print(f"g[{i}]={graphe[i][j]}, g[{j}]={graphe[j][i]}") """
- Edité par PierrotLeFou 27 août 2024 à 14:50:37
Le Tout est souvent plus grand que la somme de ses parties.
import sys
def main():
# Lecture des paramètre et initialisation du graphe.
n, a = map(int, input().split())
graphe = [[float('inf')] * n for _ in range(n)]
for i in range(n):
graphe[i][i] = 0
# Lecture des sentiers et assignation dans le graphe.
for _ in range(a):
#u, v, w = map(int, input().split())
u, v, w = map(int,sys.stdin.readline().split())
graphe[u-1][v-1] = w
graphe[v-1][u-1] = w
# Algorithme de Floyd-Warshall.
infini = float("inf")
for k in range(n):
graphe_k = graphe[k]
for i in range(n):
graphe_i = graphe[i]
graphe_ik = graphe_i[k]
if graphe_ik == infini: continue
for j in range(i+1,n):
graphe_ikj = graphe_ik + graphe_k[j]
if graphe_i[j] > graphe_ikj:
graphe_i[j] = graphe_ikj
graphe[j][i] = graphe_ikj
# Affichage des résultats.
for i in range(n):
print(*graphe[i])
main()
"""
for i in range(n):
for j in range(i+1, n):
if graphe[i][j] != graphe[j][i]: print(f"g[{i}]={graphe[i][j]}, g[{j}]={graphe[j][i]}")
"""
voici le résultat des tests
Test 1
Succès
Exécuté en 0,06 seconde.
100 %
Test 2
Succès
Exécuté en 0,06 seconde.
100 %
Test 3
Succès
Exécuté en 0,06 seconde.
100 %
Test 4
Succès
Exécuté en 0,09 seconde.
100 %
Test 5
Succès
Exécuté en 0,26 seconde.
100 %
Test 6
Succès
Exécuté en 1,74 seconde.
100 %
Test 7
Succès
Exécuté en 3,35 secondes.
100 %
Test 8
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
0 %
Test 9
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
0 %
Test 10
Échec
Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.
0 %
TOTAL
Échec
Vous avez réussi 7 tests sur 10.
70 %
ce qui est étonnant c'est au test 7 à 3.35s loin des 10s max et d'un coup au test 8 le programme est trop long ce qui veut dire qu'il dépasse les 10s
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.