P1744 Buying Discounted Items

"The Story of Love and Sorrow, Part 3 · shopping," Chapter 1.

There are shops everywhere along Zhongshan Road, which has become a point of no return for the shopaholic guru "Love-and-Sorrow" (Ai Yu Chou). There are $n$ ($n \leq 100$) shops on Zhongshan Road, and each shop’s coordinates lie between $-10000$ and $10000$. Among them, there are $m$ roads connecting pairs of shops. If there is a road, you can travel from one shop to the other, and the length of the road is the straight-line distance between the two points. Now the guru "Love-and-Sorrow" wants to find the shortest distance between two shops. Can you help compute it?

A total of $n+m+3$ lines: The first line: an integer $n$. The next $n$ lines: each line contains two integers $x$ and $y$, giving the coordinates of a shop. The next line: an integer $m$. The next $m$ lines: each line describes a road, consisting of two integers $i$ and $j$, indicating there is a road between shop $i$ and shop $j$. The next line: two integers $s$ and $t$, indicating the source shop and the target shop, respectively.

A single line: a real number (rounded to two decimal places), representing the length of the shortest path from $s$ to $t$.

Constraints: For $100 \%$ of the testdata: $2 \le n \leq 100$, $1 \le i, j, s, t \le n$, $1 \le m \leq 1000$. Translated by ChatGPT 5