P1730 Minimum Density Path

Given a weighted directed acyclic graph (DAG) with $N$ vertices and $M$ edges, followed by $Q$ queries. Each query consists of two vertices $X$ and $Y$. Compute a path from $X$ to $Y$ with minimum density, where density is defined as the sum of edge weights along the path divided by the number of edges.

The first line contains two integers $N$ and $M$. Each of the next $M$ lines contains three integers $A, B, W$, indicating there is a directed edge from $A$ to $B$ with weight $W$. The next line contains an integer $Q$. Each of the next $Q$ lines contains a query with two vertices $X$ and $Y$, as described.

For each query, output one line containing the density of the minimum-density path, rounded to $3$ decimal places. If no such path exists, output ```OMG!```.

Constraints $1 \le N \le 50$, $1 \le M \le 1000$, $1 \le W \le 10^5$, $1 \le Q \le 10^5$. Translated by ChatGPT 5