P2176 [USACO11DEC] RoadBlock S / [USACO14FEB] Roadblock G/S

Every morning, FJ walks from his house across the farm to the barn. The farm consists of $N$ fields connected by $M$ bidirectional roads, each with a certain length. FJ’s house is at field $1$, and the barn is at field $N$. No two fields are connected by multiple roads, and the graph is connected. Whenever FJ travels between fields, he always takes a path with the minimum total length. FJ’s cows, up to no good as always, decide to disrupt his morning routine. They place a stack of hay bales on one of the $M$ roads, doubling that road’s length. The cows want to choose a road to maximize the increase in FJ’s shortest path distance from home to the barn. They ask you to compute and report this maximum increase.

Line $1$: two integers $N, M$. Lines $2$ to $M+1$: the $(i+1)$-th line contains three integers $A_i, B_i, L_i$. $A_i$ and $B_i$ are the indices of the fields connected by road $i$, and $L_i$ is the length of that road.

A single integer: the maximum increase obtained by doubling exactly one road.

Sample explanation: If the length of the road between $3$ and $4$ is doubled, the shortest path changes from $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ to $1 \rightarrow 3 \rightarrow 5$. Constraints: - For $30\%$ of the testdata, $N \le 70$, $M \le 1{,}500$. - For $100\%$ of the testdata, $1 \le N \le 100$, $1 \le M \le 5{,}000$, $1 \le L_i \le 1{,}000{,}000$. Translated by ChatGPT 5