MOJ Round #1Ended |
Los estudiantes de las escuelas de Cuba se reúnen todos los años en invierno en un campamento para realizar la tradicional búsqueda de los tesoros escondidos en las cuevas. A cada competidor se le entrega un mapa (representado por un grafo orientado) con todas las cuevas de la región donde se encuentran los tesoros y los caminos que existen entre ellas. Cada cueva tiene un tesoro el cual tiene un determinado valor que el competidor obtiene si pasa por ese lugar. Es posible que no se pueda ir a todas las cuevas, pues en ocasiones los caminos son de difícil acceso. Si usted visita una cueva más de una vez solo recibe el beneficio de los valores de los tesoros la primera vez que pasó por ese lugar. Por lo tanto, el competidor debe seguir una ruta que parta del campamento hasta el destino final y debe pasar por las cuevas para recoger los tesoros obteniendo la suma máxima de todos sus valores.
Tarea
Hacer un programa que permita:
- Leer la cantidad de cuevas, el valor que tienen los tesoros en cada cueva y los caminos que existen entre las cuevas.
- Determinar cuál es la suma máxima de los valores de los tesoros que puede alcanzar un competidor al seleccionar su ruta óptima.
- Escribir el valor máximo determinado.
La entrada contiene:
Línea 1: $N$ y $M$, separados entre sí por un espacio en blanco, los cuales representan el número de cuevas y la cantidad de caminos orientados entre ellas.
Línea 2: $P_0, P_1, ..., P_{N-1}$, separados entre sí por un espacio en blanco, los cuales representan los valores de los tesoros en cada cueva. El campamento, punto inicial de la ruta tiene el número $0$ y el final tendrá el número $N - 1$.
Línea 3...M + 2: $n_1$ y $n_2$, separados entre sí por un espacio en blanco, los cuales representan un camino orientado de la cueva $n_1$ a la cueva $n_2$.
Restricciones
- $2 \leq N \leq 10000$
- $1 \leq M \leq 100000$
- $0 \leq P_i \leq 10000$
La salida contiene en una línea la suma máxima de los valores de los tesoros que puede obtener un competidor al seleccionar su ruta óptima.
El mayor valor de la suma de los tesoros se obtuvo al hacer el recorrido a través de las siguientes cuevas: $0 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 5$, dando un valor total de $12 + 2 + 7 + 8 + 0 + 13 = 42$.