1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int Maxn = 205;
pair <int,int> P[Maxn];
bool Vis[Maxn];
double H[Maxn], Cost[40005];
int Head[Maxn], Next[40005], E[40005], Cur;
int N, M, X, Y;
struct ANode
{
int X;
double Dis;
bool Vis[Maxn];
bool operator < (const ANode &Temp) const
{
return Dis + H[X] > Temp.Dis + H[Temp.X];
}
};
inline double Dis(int U, int V)
{
return sqrt(double(P[U].x - P[V].x) * double(P[U].x - P[V].x) + double(P[U].y - P[V].y) * double(P[U].y - P[V].y));
}
inline void AddEdge(int U, int V)
{
Next[++Cur] = Head[U];
Head[U] = Cur;
E[Cur] = V;
Cost[Cur] = Dis(U, V);
}
inline void SPFA()
{
for (int i = 1; i <= N; ++i) H[i] = 1e9;
queue <int> Q;
Q.push(N);
H[N] = 0;
while (!Q.empty())
{
int X = Q.front();
Vis[X] = 0;
Q.pop();
for (int i = Head[X]; i; i = Next[i])
{
if (H[E[i]] <= H[X] + Cost[i]) continue;
H[E[i]] = H[X] + Cost[i];
if (Vis[E[i]]) continue;
Vis[E[i]] = 1;
Q.push(E[i]);
}
}
}
inline double GetRoad()
{
priority_queue <ANode> Q;
ANode Now = ANode{1, 0};
Now.Vis[1] = 1;
Q.push(Now);
int Count(0);
while (!Q.empty())
{
Now = Q.top();
Q.pop();
if (Now.X == N)++Count;
if (Count == 2) return Now.Dis;
for (int i = Head[Now.X]; i; i = Next[i])
{
if (Now.Vis[E[i]]) continue;
ANode Nxt = Now;
Nxt.X = E[i], Nxt.Dis = Now.Dis + Cost[i];
Nxt.Vis[E[i]] = 1;
Q.push(Nxt);
}
}
return -1.0;
}
int main()
{
scanf("%d %d", &N, &M);
for (int i = 1; i <= N; ++i) scanf ("%d %d", &P[i].x, &P[i].y);
while (M--)
{
scanf ("%d %d", &X, &Y);
AddEdge(X, Y), AddEdge(Y, X);
}
SPFA();
double Ans = GetRoad();
if (Ans < 0.0) puts("-1");
else printf("%.2lf", Ans);
system("pause");
}
|