| Enviar | Todos los envíos | Mejores soluciones | Atrás a la lista |
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? |