[Solution] Second Flight Meta Hacker Cup Qualification Round Solution

Meta Getaways is a travel agency that deals with $N$ airports numbered $1...N$, and $M$ flight paths. Flight path $i$ connects airports $A_i$ and $B_i$ in both directions, with two direct flights operating every morning (one in each direction), and another two every evening (also one in each direction). Each of these four direct flights can carry up to $C_i$ tourists.

The first sample case is depicted above, with morning and evening flights in red and blue.

Peak travel season is here, and will last $Q$ days. For each day $i$, determine $F_i$, the maximum number of tourists who could possibly fly from airport $X_i$ to $Y_i$. Each tourist may either fly directly or take one morning and one evening flight which share an intermediate airport.

Constraints

$1 \leq T \leq 70$ $1 \leq N, M, Q \leq 200{,}000$ $1 \leq C_i \leq 10^9$ $1 \leq A_i, B_i \leq N; A_i \ne B_i$ $1 \leq X_i, Y_i \leq N; X_i \ne Y_i$ All unordered pairs $(A_i, B_i)$ within a given test case are distinct.

The sum of $Q$ across all test cases is at most $5{,}000{,}000$.

Input Format

Input begins with a single integer $T$, the number of test cases. For each case, there is first a line containing three space-separated integers $N$, $M$, and $Q$. Then, $M$ lines follow, the $i$th of which contains three space-separated integers $A_i$, $B_i$, and $C_i$. Then, $Q$ lines follow, the $i$th of which

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

contains two space-separated integers $X_i$ and $Y_i$.

Output Format

For the $i$th case, print a line containing "Case #i: " followed by $Q$ space-separated integers $F_1, ..., F_Q$.

Sample Explanation

In the first case:

• On day $1$, we must send as many tourists from airport $1$ to airport $2$. We can fly $10$ tourists direct in the morning and $10$ more at night. Only $5$ tourists can be flown from $1 \to 3$ in the morning and $3 \to 2$ in the evening (despite the evening flight capacity being $15$). Therefore, $F_1 = 10 \cdot 2 + 5 = 25$.
• On day $2$, we can fly $5$ tourists direct in the morning and evening, then fly $10$ tourists through airports $1 \to 2 \to 3$. Therefore, $F_2 = 5 \cdot 2 + 10 = 20$.
• $F_3 = 15 \cdot 2 + 5 + 7 = 42$
• $F_4 = 10 \cdot 2 + 7 = 27$
• $F_5 = 7 \cdot 2 + 10 = 24$
• On day $6$, there are no direct flights. We can fly $10$ tourists through airports $1 \to 2 \to 4$, and $5$ tourists through airports $1 \to 3 \to 4$ for a total of $F_6 = 10 + 5 = 15$ tourists.

In the second case:

• $F_1 = 10 \cdot 2 + 20 = 40$
• $F_2 = 30 \cdot 2 + 10 = 70$
• $F_3 = 0$
• $F_4 = 20 \cdot 2 + 10 = 50$
• $F_5 = 0$
• $F_6 = 0$