Burn them All

# Burn Them All ## Problem Statement You are given an undirected graph with $n$ vertices and $m$ edges. Each edge connects two vertices, say $u$ and $v$, and has a weight $d$, representing a thread of length $d$ units between $u$ and $v$. At time $t=0$, a fire is started at vertex $A$. The fire spreads along the threads. It takes $1$ unit of time for the fire to travel $1$ unit of distance along any thread. When a thread is fully burned, it means fire has traversed its entire length from either or both ends. Let $T$ be the minimum time required for all threads in the graph to be completely burned out. Your task is to find the value of $10T$. It is guaranteed that $10T$ will always be an integer. The graph is guaranteed to be connected. ## Input Format - First line: $n$ ($1 \le n \le 2 \times 10^5$) - the number of nodes in the graph. - Second line: $m$ ($1 \le m \le 2 \times 10^5$) - the number of edges in the graph. - Next $m$ lines: three integers $u, v, d$ ($1 \le u, v \le n$, $1 \le d \le 10^9$) - representing an edge between node $u$ and node $v$ with a thread of length $d$. - Last line: $A$ ($1 \le A \le n$) - the node on which the fire is initially set. ## Output Format Print the value of $10T$. ## Sample Test Cases ### Sample Input 1 ``` 2 1 1 2 2 1 ``` ### Sample Output 1 ``` 20 ``` ### Sample Input 2 ``` 3 3 1 2 2 2 3 2 1 3 6 1 ``` ### Sample Output 2 ``` 50 ``` ### Sample Input 3 ``` 3 3 1 2 2 1 3 2 2 3 1 1 ``` ### Sample Output 3 ``` 25 ``` ## Constraints - $1 \le n \le 2 \times 10^5$ - $1 \le m \le 2 \times 10^5$ - $1 \le u, v \le n$ - $1 \le d \le 10^9$ - $1 \le A \le n$ - The graph is connected. - Time limit: $2$ seconds - Memory limit: $256$ MB ## Explanation For all sample cases, first, we compute $D_x$, the shortest path distance from the starting node $A$ to every other node $x$ in the graph. This can be done using Dijkstra's algorithm. Then, for each edge $(u,v)$ with length $d$, we calculate the time it takes to fully burn: $\frac{D_u + D_v + d}{2}$. The value of $T$ is the maximum of these burning times over all edges. ### Sample 1: Starting node $A=1$. The distances are $D_1=0$, $D_2=2$. For edge $(1,2)$ with $d=2$, the burn time is $\frac{0+2+2}{2} = 2$. So $T=2$, and $10T=20$. ### Sample 2: Starting node $A=1$. The shortest path distances are $D_1=0$, $D_2=2$ (via $1 \to 2$), $D_3=4$ (via $1 \to 2 \to 3$). - Edge $(1,2)$, $d=2$: burn time $\frac{0+2+2}{2} = 2$. - Edge $(2,3)$, $d=2$: burn time $\frac{2+4+2}{2} = 4$. - Edge $(1,3)$, $d=6$: burn time $\frac{0+4+6}{2} = 5$. The maximum burn time is $T=\max(2,4,5)=5$. So $10T=50$. ### Sample 3: Starting node $A=1$. The shortest path distances are $D_1=0$, $D_2=2$ (via $1 \to 2$), $D_3=2$ (via $1 \to 3$). - Edge $(1,2)$, $d=2$: burn time $\frac{0+2+2}{2} = 2$. - Edge $(1,3)$, $d=2$: burn time $\frac{0+2+2}{2} = 2$. - Edge $(2,3)$, $d=1$: burn time $\frac{2+2+1}{2} = 2.5$. The maximum burn time is $T=\max(2,2,2.5)=2.5$. So $10T=25$.