Problem
En un gráfico ponderado dirigido, los vértices se numeran del 1 al n. Si i<j, entonces hay una arista desde el vértice i hasta el vértice j cuyo peso está determinado por la fórmula \(wt(i,j)=(179i+719j)\ mod \ 1000 - 500 \). Determine el peso del camino más corto que va desde el vértice 1 al vértice n.
Entrada:
El programa recibe un único número n (2≤n≤13000) como entrada.
Salida:
El programa debe generar un único entero: el peso de la ruta más corta desde el vértice 1 hasta el vértice n en el columna.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
2 |
117 |
| 2 |
3 |
-164 |