Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AI_DIJKS - Dijkstra

Dijkstra

Dado un grafo dirigido y ponderado. Encontrar la menor distancia desde un nodo dado hasta otro.

Input

La primera linea de entrada contiene 3 números: N, S y F (1 ≤ N ≤ 2000, 1 ≤ S, F ≤ N) donde N es el número de vértices, S es el vértice inicial y F es el vértice final.

En las siguientes N lineas, N números siguen, representando la matriz de adyacencia del grafo. Donde  - 1 representa la ausencia de un arco entre dos vértices y cualquier entero no negativo que no excede 10 000 representa la ponderación de ese arco. La diagonal principal de la matriz siempre es cero.

Output

Imprimir la distancia deseada o  - 1, si el camino no existe.

Sample test(s)

Input
3 1 2
0 -1 2
3 0 -1
-1 4 0
Output
6

Adicionado por:Gabriel Rea Velasco
Fecha:2013-09-03
Tiempo límite:1s
Límite del código fuente:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Lenguajes:C CSHARP C++ 4.3.2 CPP CPP14 JAVA
Fuente:Abierto de Informatica 2013 - Preliminar

ocultar comentarios
2014-11-03 01:45:14 Diego Nuñez
Creo q hay algo mal con la descripcion del problema :\
2014-06-14 19:44:47 hicask
Lo unico critico que yo creo que hay en este problema, es en la condicion que verifica que exista una arista entre 2 nodos, la condicion debe ser con -1, no con <0.
2014-04-23 20:00:16 Alberto Suxo
Quizá sería bueno tomar en cuenta lo que dice el planteamiento del problema:
"Donde  - 1 representa la ausencia de ...."
2013-12-02 22:28:16 Marinito
ayuda... el caso 11 es un caso especial? mi programa se keda en ese caso
2013-10-25 01:32:35 santiago
tienen algún caso critico, o engañoso?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.