Problem

9 /10


Floyd - existence

Theory Click to read/hide

Le chemin à travers le cycle du poids négatif devient impossible.

Problem

On vous donne un graphique pondéré orienté. À l'aide de sa matrice de contiguïté, vous devez déterminer pour chaque paire de sommets s'il existe ou non un chemin le plus court entre eux.
 
Commentaire : Le chemin le plus court peut ne pas exister pour deux raisons :
  • Il n'y a pas de chemins
  • Il existe des chemins de poids arbitrairement petit
     
Entrée
La première ligne du fichier d'entrée contient un seul nombre : N (1 <=N <=100) — le nombre de sommets du graphe. Les N lignes suivantes contiennent N nombres chacune — matrice d'adjacence du graphe (le jième nombre de la iième ligne correspond au poids de l'arête du sommet i au sommet j) : le chiffre 0 signifie qu'il n'y a pas d'arête, et tout autre nombre — la présence d'une arête du poids correspondant. Tous les nombres modulo ne dépassent pas 100.
 
Sortie
Imprime N lignes de N nombres. Le jième nombre de la iième ligne doit correspondre au chemin le plus court du sommet i au sommet j. Le nombre doit être 0 s'il n'y a pas de chemin, 1 s'il y a un chemin le plus court et 2 s'il y a des chemins mais il y a des chemins de poids arbitrairement petit.

Exemples
5
0 1 2 0 0
1 0 3 0 0
2 3 0 0 0
0 0 0 0 -1
0 0 0 -1 0 
1 1 1 0 0 
1 1 1 0 0 
1 1 1 0 0 
0 0 0 2 2 
0 0 0 2 2 
# Entrée Sortie
1

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!