P1491 Meeting Location
Background
每次有大的活动,大家都要在一起“聚一聚”,不管是去好乐迪,还是避风塘,或者汤姆熊,大家都要玩的痛快。还记得心语和花儿在跳舞机上的激情与释放,还记得草草的投篮技艺是如此的高超,还记得狗狗的枪法永远是 S ……还有不能忘了,胖子的歌声永远是让我们惊叫的!!
今天是野猫的生日,所以想到这些也正常,只是因为是上学日,没法一起去玩了。但回忆一下那时的甜蜜总是一种幸福嘛。。。
但是每次集合的时候都会出现问题!野猫是公认的“路盲”,野猫自己心里也很清楚,每次都提前出门,但还是经常迟到,这点让大家很是无奈。后来,野猫在每次出门前,都会向花儿咨询一下路径,根据已知的路径中,总算能按时到了。
Description
Every time there is a big hangout, everyone gets together no matter if it is at Haoledi, Bifengtang, or Tangmuxiong, and we all have a blast. We still remember Xinyu and Hua'er’s passion and release on the dance machine, remember how amazing Caocao’s basketball shooting was, remember how Gougou’s aim was always S... and we must not forget that Pangzi’s singing always made us scream in surprise!
Today is Wildcat’s birthday, so it’s normal to think of all this. It’s just a school day, so we can’t go out together. But recalling those sweet times is still a kind of happiness.
However, every time we meet up, there is a problem! Wildcat is a recognized “road-blind” person. Wildcat knows this well, always leaving early, yet still often arriving late, which leaves everyone helpless. Later, before each trip, Wildcat would consult Hua'er about the route. Based on known routes, he could finally arrive on time.
Now here is the problem: given the coordinates of $n$ points, where the first one is Wildcat’s starting position and the last one is the group’s meeting position, and given which positions are connected. From the start to the meeting point, Wildcat will always choose a shortest route. If Wildcat does not find the shortest route, he will take the second-shortest route. Please help Wildcat find the length of this second-shortest path.
In particular, the chosen second-shortest path will not visit the same vertex more than once, even if allowing repeated visits to the same vertex could make it shorter.
Input Format
The first line contains two integers $n$ ($1 \le n \le 200$) and $m$ ($1 \le m \le 10000$), indicating there are $n$ points and $m$ roads in total. The next $n$ lines each contain two numbers $x_i$, $y_i$ ($-500 \le x_i, y_i \le 500$), representing the coordinates of the $i$-th point. The following $m$ lines each contain two integers $p_j$, $q_j$ ($1 \le p_j, q_j \le n$), indicating that there is a road between these two points. There are no multiple edges in the testdata; self-loops may exist.
Output Format
Output a single line containing one number: the distance of the second-shortest route (keep two decimal places). If there are multiple shortest paths, then the answer is the shortest-path length. If no second-shortest path exists, output `-1`.
Explanation/Hint
Translated by ChatGPT 5