Este problema se enfoca en encontrar la distancia mínima en un grafo utilizando una técnica de "saltos" o "caminos acelerados", combinada con un algoritmo de ruta más corta entre todos los pares de nodos. La clave reside en la aplicación de la programación dinámica con un enfoque de exponenciación binaria (doubling) para construir aristas de costo unitario que cubren distancias de potencia de dos.

Preprocesamiento con Duplicación (Doubling)

La idea central es determinar si se puede viajar entre dos puntos mediante una secuencia de saltos, donde cada salto tiene una longitud que es una potencia de 2. Mantenemos un arreglo tridimensional conectado[u][v][k] que indica si existe un camino directo desde el nodo u al nodo v cuya longitud es exactamente 2^k "pasos" utilizando la máquina de teletransporte. Un "paso" aquí significa el uso de la máquina, independientemente de la distancia real cubierta.

La inicialización comienza con k=0. Si existe una conexión directa (arista original) de u a v, entonces conectado[u][v][0] es verdadero, y la distancia inicial entre u y v es 1 (un uso de la máquina).

Para k > 0, podemos construir conexiones de longitud 2^k. Una conexión de u a v de longitud 2^k es posible si existe un nodo intermedio x tal que:

• conectado[u][x][k-1] es verdadero (hay una conexión de u a x de longitud 2^(k-1)).
• conectado[x][v][k-1] es verdadero (hay una conexión de x a v de longitud 2^(k-1)).

Si ambas condiciones se cumplen, entonces conectado[u][v][k] se establece como verdadero, y esta nueva "súper-arista" de u a v también tiene un costo de 1 unidad de viaje.

Algoritmo de Floyd-Warshall

Una vez que todas las posibles conexiones directas y de "súper-aristas" (cada una con un costo de 1 unidad de viaje) se han establecido, el problema se reduce a encontrar la ruta más corta entre todos los pares de nodos en este grafo modificado. Dado que el número de nodos N es pequeño (hasta 50), el algoritmo de Floyd-Warshall es una solución eficiente para este propósito. El algoritmo calculará el número mínimo de "usos de la máquina" (saltos) para ir de cualquier nodo a cualquier otro.

Implementación en Java

El código utiliza un arreglo minSaltos[N][N] para almacenar la distancia mínima (número de saltos) entre dos nodos y puedeSaltar[N][N][M] para la conectividad de potencia de 2. La función inicializarConexiones() implementa el paso de duplicación, y ejecutarFloydWarshall() aplica el algoritmo de Floyd-Warshall.

import java.io.*;
import java.util.Arrays;

public class Main implements Runnable {

   static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
   static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
   static final int MAX_NODOS = 55;
   static final int MAX_POTENCIAS_DOS = 32; // Log2(Max_Distancia) + 1, ~log2(50) + 1 = 6 + 1 = 7, pero 32 es un margen seguro
   
   // minSaltos[i][j] = número mínimo de saltos para ir de i a j
   static int[][] minSaltos = new int[MAX_NODOS][MAX_NODOS]; 
   // puedeSaltar[i][j][k] = true si hay un camino de i a j de longitud 2^k
   static boolean[][][] puedeSaltar = new boolean[MAX_NODOS][MAX_NODOS][MAX_POTENCIAS_DOS]; 
   
   static int numNodos, numAristasIniciales;

   public static void main(String[] args) {
       new Thread(null, new Main(), "", 1 << 29).start();
   }

   public static int leerEntero() throws IOException {
       cin.nextToken();
       return (int) cin.nval;
   }

   // Inicializa las conexiones usando la técnica de duplicación
   public static void inicializarConexiones() {
       for (int k = 1; k < MAX_POTENCIAS_DOS; k++) {
           for (int nodoIntermedio = 1; nodoIntermedio <= numNodos; nodoIntermedio++) {
               for (int inicio = 1; inicio <= numNodos; inicio++) {
                   for (int fin = 1; fin <= numNodos; fin++) {
                       if (puedeSaltar[inicio][nodoIntermedio][k - 1] && puedeSaltar[nodoIntermedio][fin][k - 1]) {
                           puedeSaltar[inicio][fin][k] = true;
                           minSaltos[inicio][fin] = 1; // Un salto de cualquier longitud cuenta como 1 uso
                       }
                   }
               }
           }
       }
   }

   // Ejecuta el algoritmo de Floyd-Warshall para encontrar los caminos más cortos
   public static void ejecutarFloydWarshall() {
       for (int k = 1; k <= numNodos; k++) { // Nodo intermedio
           for (int i = 1; i <= numNodos; i++) { // Nodo de inicio
               for (int j = 1; j <= numNodos; j++) { // Nodo de fin
                   // Si el camino a través de k es más corto
                   if (minSaltos[i][k] != Integer.MAX_VALUE && minSaltos[k][j] != Integer.MAX_VALUE) {
                       minSaltos[i][j] = Math.min(minSaltos[i][j], minSaltos[i][k] + minSaltos[k][j]);
                   }
               }
           }
       }
   }

   @Override
   public void run() {
       try {
           numNodos = leerEntero();
           numAristasIniciales = leerEntero();

           // Inicializar distancias: infinito para no conectados, 0 para sí mismo
           for (int i = 1; i <= numNodos; i++) {
               Arrays.fill(minSaltos[i], Integer.MAX_VALUE);
               minSaltos[i][i] = 0; // Distancia a sí mismo es 0 saltos
           }

           // Leer aristas iniciales (longitud 2^0 = 1)
           for (int i = 1; i <= numAristasIniciales; i++) {
               int u = leerEntero();
               int v = leerEntero();
               puedeSaltar[u][v][0] = true;
               minSaltos[u][v] = 1; // Un salto directo
           }

           inicializarConexiones();
           ejecutarFloydWarshall();
           
           cout.println(minSaltos[1][numNodos]);
           cout.flush();

       } catch (IOException e) {
           throw new RuntimeException(e);
       }
   }
}

Cálculo de Probabilidades en un Juego de Extracción de Bolas

Este problema es un clásico de programación dinámica sobre probabilidades, modelando un juego entre una Princesa y un Dragón. Ambos extraen bolas de una bolsa que contiene bolas blancas (W) y negras (B), y el objetivo es determinar la probabilidad de que la Princesa gane.

Reglas del Juego

• La Princesa comienza el juego.
• Si la Princesa saca una bola blanca: Ella gana.
• Si la Princesa saca una bola negra: La bola negra se retira, y es el turno del Dragón.
• Si el Dragón saca una bola blanca: Él gana (la Princesa pierde).
• Si el Dragón saca una bola negra: La bola negra se retira. Luego, el Dragón retira una bola negra adicional de la bolsa (la "come"). Después de esto, es el turno de la Princesa nuevamente.

Programación Dinámica para la Probabilidad

Definimos probVictoriaP[w][b] como la probabilidad de que la Princesa gane, dado que es su turno y hay w bolas blancas y b bolas negras en la bolsa.

Casos Base:

• probVictoriaP[w][0] = 1.0 para w > 0: Si solo quedan bolas blancas, la Pricnesa saca una y gana.
• probVictoriaP[0][b] = 0.0 para b > 0: Si no quedan bolas blancas, la Princesa (o el Dragón) solo puede sacar negras, y la Princesa nunca gana.

Transiciones:

Para calcular probVictoriaP[w][b]:

1. La Princesa saca una bola blanca (W):

   • Probabilidad: w / (w + b)
   • Resultado: La Princesa gana.
   • Contribución a probVictoriaP[w][b]: w / (w + b)

2. La Princesa saca una bola negra (B):

   • Probabilidad: b / (w + b)
   • Resultado: La bola negra se retira. Quedan w blancas y b-1 negras. Es el turno del Dragón.

   Ahora consideramos lo que sucede cuando es el turno del Dragón con w blancas y b-1 negras:

   • El Dragón saca una bola blanca (W):

     • Probabilidad: w / (w + b - 1) (si w+b-1 > 0).
     • Resultado: El Dragón gana (la Princesa pierde).
     • Contribución a probVictoriaP[w][b] desde este camino: 0.

   • El Dragón saca una bola negra (B):

     • Probabilidad: (b - 1) / (w + b - 1) (si b-1 > 0 y w+b-1 > 0).
     • Resultado: La bola negra se retira. Quedan w blancas y b-2 negras. El Dragón come una bola negra adicional. Quedan w blancas y b-3 negras. Es el turno de la Princesa.
     • Contribución a probVictoriaP[w][b] desde este camino: (b / (w + b)) * ((b - 1) / (w + b - 1)) * probVictoriaP[w][max(0, b - 3)]
     • Nota: max(0, b - 3) se usa para manejar el caso donde b - 3 sería negativo, significando que todas las bolas negras han sido consumidas. Si b-3 < 0, entonces probVictoriaP[w][0] = 1.0 (si w > 0).

La recurrencia combinada es:

probVictoriaP[w][b] = (double)w / (w + b)  // Princesa saca W y gana
                  + ((double)b / (w + b)) *         // Princesa saca B, turno del Dragón
                    ( ((double)(b - 1) / (w + b - 1)) * // Dragón saca B
                      ( (b - 3 >= 0) ? probVictoriaP[w][b - 3] : 1.0 ) // Princesa juega de nuevo
                    );
   

Esta fórmula se aplica iterativamente, comenzando por los casos base y construyendo la solución para w y b crecientes.

import java.io.*;
import java.util.Locale; // Para String.format con punto decimal

public class Main implements Runnable {

   static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
   static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
   static int bolasBlancasIniciales, bolasNegrasIniciales;
   static final int MAX_BOLAS = (int) (1e3 + 10);
   static double[][] probVictoriaP = new double[MAX_BOLAS][MAX_BOLAS];

   public static void main(String[] args) {
       new Thread(null, new Main(), "", 1 << 29).start();
   }

   public static int leerEntero() throws IOException {
       cin.nextToken();
       return (int) cin.nval;
   }

   @Override
   public void run() {
       try {
           bolasBlancasIniciales = leerEntero();
           bolasNegrasIniciales = leerEntero();

           // Casos base:
           // Si solo hay bolas blancas, la Princesa siempre gana.
           for (int w = 1; w <= bolasBlancasIniciales; w++) {
               probVictoriaP[w][0] = 1.0;
           }
           // Si solo hay bolas negras, la Princesa nunca puede ganar.
           // (probVictoriaP[0][b] ya es 0.0 por inicialización de array)

           // Llenar la tabla de DP
           for (int w = 0; w <= bolasBlancasIniciales; w++) {
               for (int b = 1; b <= bolasNegrasIniciales; b++) {
                   // Si no quedan bolas blancas, la Princesa no puede ganar.
                   if (w == 0) {
                       probVictoriaP[w][b] = 0.0;
                       continue;
                   }

                   // Escenario 1: Princesa saca una bola blanca.
                   // Probabilidad de sacar blanca: w / (w+b). La Princesa gana.
                   probVictoriaP[w][b] = (double) w / (w + b);

                   // Escenario 2: Princesa saca una bola negra.
                   // Probabilidad de sacar negra: b / (w+b). Es el turno del Dragón.
                   // Consideramos solo si el Dragón puede sacar una bola negra y la Princesa puede volver a jugar.
                   // Requiere al menos 1 bola negra para Princesa sacar, y al menos 1 bola negra para Dragón sacar.
                   // Y para que D coma una, debe haber al menos 2 negras para D sacar, y 1 para comer.
                   // En total, b >= 3 bolas negras para que el ciclo completo "P saca B -> D saca B -> D come B -> P juega" sea posible.
                   if (b >= 1) { // Princesa puede sacar B
                       double probP_saca_B = (double) b / (w + b);

                       if (w + b - 1 > 0) { // Hay bolas para que el Dragón saque
                           // El Dragón tiene (w, b-1) bolas.
                           // Si Dragón saca W, Princesa pierde.
                           // Si Dragón saca B:
                           if (b - 1 >= 1) { // Dragón puede sacar B
                               double probD_saca_B = (double)(b - 1) / (w + b - 1);
                               
                               // Dragón saca B, luego come otra B.
                               // Total de B eliminadas: 1 (por Princesa) + 1 (por Dragón) + 1 (Dragón come) = 3 B.
                               // La Princesa vuelve a jugar con (w, b-3) bolas.
                               double probP_gana_despues_D = (b - 3 >= 0) ? probVictoriaP[w][b - 3] : 1.0; // Si b-3 < 0, significa que todas las B se agotaron, P gana (si w > 0).

                               probVictoriaP[w][b] += probP_saca_B * probD_saca_B * probP_gana_despues_D;
                           }
                       }
                   }
               }
           }
           
           cout.println(String.format(Locale.US, "%.9f", probVictoriaP[bolasBlancasIniciales][bolasNegrasIniciales]));
           cout.flush();

       } catch (IOException e) {
           throw new RuntimeException(e);
       }
   }
}

Esperanza de Ruta en un DAG mediante Programación Dinámica

Este problema nos pide calcular la longitud esperada de un camino desde un nodo inicial (generalmente el nodo 1) hasta un nodo final (el nodo N) en un grafo acíclico dirigido (DAG). La particularidad es que, en cada nodo con múltiples aristas salientes, se elige una arista uniformemente al azar.

Concepto de Esperanza y Programación Dinámica

La esperanza de una variable aleatoria es el promedio ponderado de sus posibles valores, donde los pesos son sus probabilidades. En este contexto, la esperanza de la longitud de un camino desde un nodo u hasta N, denotada como E[u], se calcula como la suma de las esperanzas de los caminos a través de sus vecinos:

E[u] = Σ (P(u → v) * (costo(u, v) + E[v]))

Donde P(u → v) es la probabilidad de elegir la arista (u, v). Dado que las aristas se eligen uniformemente al azar, si el nodo u tiene grado_salida(u) aristas salientes, entonces P(u → v) = 1 / grado_salida(u) para cada vecino v.

Por lo tanto, la fórmula se simplifica a:

E[u] = Σ_{v ∈ sucesores(u)} ( (costo(u, v) + E[v]) / grado_salida(u) )

Algoritmo de Recorrido en Grafo

Para calcular E[u], necesitamos conocer E[v] para todos los sucesores v de u. Esto sugiere un enfoque de programación dinámica que procesa los nodos en orden topológico inverso, es decir, empezando desde el nodo final N y retrocediendo.

1. Estado Base: La esperanza de la longitud desde el nodo final N hasta N es 0. Es decir, E[N] = 0.
2. Construcción del Grafo Inverso: Para facilitar el recorrido topológico inverso, se construye un grafo donde todas las aristas están invertidas. Si originalmente hay una arista u → v, en el grafo inverso habrá una arista v → u. También necesitamos calcular el grado de salida de cada nodo en el grafo original (número de aristas que parten de él).
3. Ordenación Topológica Inversa: Se realiza una ordenación topológica en el grafo inverso. Esto se logra inicializando una cola con el nodo final N (que tendrá un grado de entrada de 0 en el grafo inverso si no hay ciclos).
4. Cálculo de la Esperanza: Mientras se procesan los nodos en el orden topológico inverso:
   • Cuando se extrae un nodo curr de la cola (significando que E[curr] ya está finalizado o es 0), se itera sobre sus vecinos en el grafo inverso. Estos vecinos son los predecesores de curr en el grafo original.
   • Para cada predecesor prev con una arista prev → curr (de costo peso), se actualiza E[prev]: E[prev] += (E[curr] + peso) / grado_salida[prev].
   • Se decrementa el grado de "sucesores pendientes" de prev. Si este contador llega a cero, significa que E[prev] se ha acumulado por todos sus sucesores, y prev puede ser añadido a la cola para su procesamiento.

Este proceso garantiza que E[v] se conoce antes de usarse para calcular E[u] si u → v es una arista.

import java.io.*;
import java.util.*;

public class Main implements Runnable {

   static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
   static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
   static int numNodos, numAristas;
   static final int MAX_NODOS = (int) (1e5 + 10);
   
   // Almacena el grado de salida de cada nodo en el grafo original
   static int[] gradoSalidaOriginal = new int[MAX_NODOS]; 
   // Almacena la esperanza de longitud desde el nodo i hasta el nodo N
   static double[] expectativa = new double[MAX_NODOS]; 
   
   // Cola para la ordenación topológica inversa
   static Queue<Integer> colaProcesamiento = new LinkedList<>(); 
   // Lista de adyacencia para el grafo inverso (v -> u si u -> v en original)
   static Vector<Arista>[] adjInversa = new Vector[MAX_NODOS]; 

   public static void main(String[] args) {
       new Thread(null, new Main(), "", 1 << 29).start();
   }

   public static int leerEntero() throws IOException {
       cin.nextToken();
       return (int) cin.nval;
   }

   public static void calcularEsperanza() {
       // El nodo N ya tiene expectativa[N] = 0.0, y es el primero en la cola.
       while (!colaProcesamiento.isEmpty()) {
           Integer nodoActual = colaProcesamiento.poll(); // Nodo actual procesado (E[nodoActual] ya está finalizado)

           // Iterar sobre los predecesores de nodoActual en el grafo original
           // (que son los vecinos en el grafo inverso)
           for (Arista aristaInv : adjInversa[nodoActual]) {
               int predecesor = aristaInv.destino; // 'destino' en Arista en realidad es el origen original
               int pesoArista = aristaInv.peso;

               // Si el predecesor tiene un grado de salida mayor que 0 (evitar división por cero)
               if (gradoSalidaOriginal[predecesor] > 0) {
                   // Contribución del camino que pasa por nodoActual
                   expectativa[predecesor] += (expectativa[nodoActual] + pesoArista) / gradoSalidaOriginal[predecesor];
               }
               
               // Decrementar el "grado de entrada" para el orden topológico inverso
               // Esto es, marcamos que un sucesor de 'predecesor' ya fue procesado.
               gradoSalidaOriginal[predecesor]--; // Este se usa como contador de sucesores pendientes
               
               // Si todos los sucesores de 'predecesor' ya fueron procesados,
               // entonces 'predecesor' está listo para ser añadido a la cola.
               if (gradoSalidaOriginal[predecesor] == 0) {
                   colaProcesamiento.add(predecesor);
               }
           }
       }
   }

   @Override
   public void run() {
       try {
           numNodos = leerEntero();
           numAristas = leerEntero();
           
           // Inicializar las listas de adyacencia
           for (int i = 1; i <= numNodos; i++) {
               adjInversa[i] = new Vector<>();
           }
           
           // Leer aristas y construir el grafo inverso, y calcular grados de salida originales
           for (int i = 1; i <= numAristas; i++) {
               int u = leerEntero(); // Origen
               int v = leerEntero(); // Destino
               int peso = leerEntero(); // Peso de la arista u -> v
               
               adjInversa[v].add(new Arista(u, peso)); // Añadir arista v -> u en el grafo inverso
               gradoSalidaOriginal[u]++; // Contar aristas salientes de u en el grafo original
           }

           // Inicializar la cola con el nodo final (N) para empezar el recorrido inverso
           colaProcesamiento.add(numNodos);
           expectativa[numNodos] = 0; // La esperanza del nodo final a sí mismo es 0

           calcularEsperanza();

           cout.println(String.format(Locale.US, "%.2f", expectativa[1])); // Resultado para el nodo 1
           cout.flush();

       } catch (IOException e) {
           throw new RuntimeException(e);
       }
   }

   // Clase auxiliar para representar una arista en el grafo inverso
   // 'destino' aquí es el origen de la arista en el grafo original
   static class Arista {
       int destino; // Representa el nodo 'u' si la arista original era u -> v (y ahora es v -> u)
       int peso;    // Peso de la arista original u -> v

       public Arista(int destino, int peso) {
           this.destino = destino;
           this.peso = peso;
       }
   }
}