Problem

3 /10


Le chemin le plus long

Problem

Étant donné un graphe orienté dont les arêtes sont affectées de poids non négatifs (longueurs). Nous devons trouver deux sommets, le chemin le plus court entre lesquels a la plus grande longueur.
 
Entrée
La première ligne contient le nombre de sommets N ≤50. Vient ensuite la matrice d'adjacence du graphe, c'est-à-dire N lignes contenant chacune N nombres. Le jième nombre dans la iième ligne de la matrice de contiguïté spécifie la longueur de l'arête menant du iième sommet au jième. Les longueurs peuvent prendre n'importe quelle valeur de 0 à 1000000. Il est garanti qu'il y a des zéros sur la diagonale principale de la matrice.
 
Sortie
Imprimer un seul numéro – la longueur du chemin souhaité.

Exemples
3
0 7 3
7 0 10
2 215 0
# Entrée Sortie
1 10
 

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!