P15805 [GESP202603 Level 8] Subgraph Shortest Paths

Related multiple-choice and true/false questions: .

Given a **weighted undirected graph** $G$ with $n$ nodes and $m$ edges, the nodes are numbered $1, 2, \dots, n$ in order. The $i$-th edge ($1 \le i \le m$) connects two nodes numbered $u_i$ and $v_i$, with weight $w_i$. For given $1 \le \ell \le r \le n$, construct a subgraph $G(\ell, r)$ of $G$ as follows: - Keep the nodes in $G$ whose numbers are in the interval $[\ell, r]$. Delete all other nodes whose numbers are not in $[\ell, r]$ and the edges incident to them. The remaining nodes and edges form the subgraph $G(\ell, r)$. For any nodes $u, v$ in $G(\ell, r)$, we have $\ell \le u, v \le r$. Let the shortest distance between $u$ and $v$ in the subgraph $G(\ell, r)$ be $d(\ell, r, u, v)$. In particular, if $u$ and $v$ are not connected in $G(\ell, r)$, then define $d(\ell, r, u, v) = 0$. You need to compute $\sum_{\ell=1}^{n} \sum_{r=\ell}^{n} \sum_{u=\ell}^{r} \sum_{v=u}^{r} d(\ell, r, u, v)$ modulo $10^9$. - In this problem, the English letter $l$ is written as $\ell$ to avoid confusion between the letter $l$ and the digit $1$.

The first line contains two positive integers $n, m$, representing the number of nodes and the number of edges. The next $m$ lines: the $i$-th line ($1 \le i \le m$) contains three positive integers $u_i, v_i, w_i$, representing an edge connecting nodes $u_i$ and $v_i$ with weight $w_i$.

Output one line with one integer, representing $\sum_{\ell=1}^{n} \sum_{r=\ell}^{n} \sum_{u=\ell}^{r} \sum_{v=u}^{r} d(\ell, r, u, v)$ modulo $10^9$.

For $40\%$ of the testdata, it is guaranteed that $2 \le n \le 20$. For all testdata, it is guaranteed that $2 \le n \le 100$, $2 \le m \le \frac{n(n-1)}{2}$, $1 \le u_i, v_i \le n$, and $1 \le w_i \le 10^6$. There may be multiple edges in the graph. Translated by ChatGPT 5