Examen de pociones
Mañana es el examen de pociones. Lo bueno es que no tienes que estudiar porque ya te lo sabes. Lo malo es que te lo sabes porque… eres el profesor de la asignatura y… aún tienes el examen sin poner. Estás seguro de que tus alumnos estarán ya dormidos tan a gusto mientras tú estás ahí dando vueltas a qué examen poner para que no suspendan todos.
Después de mucho pensar ya sabes qué poción vas a pedir que te hagan y ahora tienes que decidir cuánto tiempo les dejas en total para hacerlo. Ese cálculo no es fácil porque una misma poción puede hacerse de muchas formas distintas y quieres que, elijan la forma que elijan, puedan terminar en plazo.
En general, las pociones se componen de pasos distintos. Cada uno de los pasos consiste en una acción (de duración despreciable) como echar algún ingrediente en el caldero o poner el fuego más alto. Tras esa acción hay que esperar un tiempo determinado mientras se remueve con un cucharón, se recita un conjuro, se baila una danza o cualquier otra cosa. La espera (y lo que se haga en ella) lleva a la poción a un estado distinto al original en el que o bien el brebaje ya está listo o bien toca echar otro ingrediente y volver a esperar.
Como buen profesor de pociones, el proceso completo lo tienes bien documentado: para cada estado posible del caldero y la poción que contiene, sabes qué ingredientes hay que echar, de cuántas formas distintas se puede esperar y, para cada posible espera, cuánto dura y a qué estado de la poción conduce.
Con toda esa información, lo que queda es pan comido. Hay que calcular el tiempo máximo de elaboración de la poción, hacer el enunciado, pasarlo a los pergaminos de examen y ya podrás irte a dormir.
Entrada
La entrada está compuesta de distintos casos de prueba
Cada caso de prueba comienza con una línea con dos números: el número de estados posibles en los que puede estar la poción (hasta 10.000) y el número de transiciones posibles entre estados (al menos una no más de 100.000). Tras eso aparece una línea por cada transición indicando el estado origen y destino (números entre 1 y el número total de estados) y el tiempo que hay que esperar (hasta 10.000)
Se garantiza que la receta nunca "va hacia atrás", es decir que ninguna secuencia de acciones hace que el brebaje vuelva a estar como estuvo anteriormente.
Ten en cuenta que puede haber distintas alternativas para la primera acción a realizar sobre el caldero vacío y que hay distintos estados que se consideran que tienen la receta terminada. Además los distintos caminos para hacer la receta podrían no tener ningún estado común.
Tras el último caso de prueba viene una línea con dos ceros que no debe procesarse.
Salida
Por cada caso de prueba se escribirán dos líneas. En la primera se indicará la duración mínima del examen (o lo que es lo mismo, la duración máxima en la elaboración de la receta). La segunda línea contiene cuál es el camino de estados por los que pasa el brebaje con esa elaboración. Si hay varios caminos de coste máximo se escribirá aquel cuyo primer nodo tenga un identificador más pequeño en la entrada; si aún así sigue habiendo varios, se escribirá el que tenga el segundo nodo más pequeño y así sucesivamente.
Entrada de ejemplo
5 4 1 2 1 2 3 1 3 4 1 3 5 1 5 6 1 2 3 2 3 3 1 4 5 4 2 2 4 5 1 5 3 1 4 2 1 2 10 3 4 20 0 0
Salida de ejemplo
3 1 2 3 4 10 1 4 2 3 20 3 4