Module: Algorithme de Dijkstra


Problem

2 /14


Dijkstra

Theory Click to read/hide

Problem

On vous donne un graphique pondéré orienté. Trouver la distance la plus courte entre un sommet donné et un autre.
 
Entrée
La première ligne contient trois nombres : N, S et F (1≤ N≤ 100, 1≤ S, F≤ N), où N – nombre de sommets du graphe, S – sommet initial, et F – final. Dans les N lignes suivantes, entrez N nombres chacun, n'excédant pas 100, – matrice d'adjacence graphique, où -1 signifie qu'il n'y a pas d'arête entre les sommets et tout nombre non négatif – la présence d'une arête de poids donné. Des zéros sont écrits sur la diagonale principale de la matrice.
Sortie
Il est nécessaire d'afficher la distance souhaitée ou -1 s'il n'y a pas de chemin entre les sommets spécifiés.

Exemples
3 2 1
0 1 1
4 0 1
2 1 0
# Entrée Sortie
1 3

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!