Module: Algorithme de Dijkstra


Problem

9/14

Algorithme de Dijkstra en O(M logN) avec priority_queue : Start (C++)

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, M, S et F (1≤ N≤ 100, 1≤ S, F≤ N), où N – nombre de sommets du graphe, M – nombre de côtes,  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
# Entrée Sortie
1 4 4 3 4
3 1 3
1 2 3
2 4 3
3 4 10
9