44 lines
1.1 KiB
C++
44 lines
1.1 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
int o(int t) {
|
||
return t * t;
|
||
}
|
||
const int N = 110;
|
||
int n, m, x[N], y[N];
|
||
double g[N][N];
|
||
|
||
int main() {
|
||
cin >> n;
|
||
for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
|
||
|
||
// double类型的数组，初始化不能用memset!!!!
|
||
// memset(g, 0x3f, sizeof g);
|
||
// for (int i = 0; i <= n; i++) g[i][i] = 0;
|
||
|
||
// 需要用二重循环进行初始化
|
||
for (int i = 1; i <= n; i++)
|
||
for (int j = 1; j <= n; j++) {
|
||
if (i == j)
|
||
g[i][j] = 0;
|
||
else
|
||
g[i][j] = 0x3f3f3f3f;
|
||
}
|
||
|
||
cin >> m;
|
||
int l, r;
|
||
while (m--) {
|
||
cin >> l >> r;
|
||
g[r][l] = g[l][r] = sqrt((double)o(x[l] - x[r]) + (double)o(y[l] - y[r])); // 勾股定理
|
||
}
|
||
|
||
// floyd
|
||
for (int k = 1; k <= n; k++)
|
||
for (int i = 1; i <= n; i++)
|
||
for (int j = 1; j <= n; j++)
|
||
if (g[i][j] > g[i][k] + g[k][j]) g[i][j] = g[i][k] + g[k][j];
|
||
|
||
cin >> l >> r;
|
||
printf("%.2lf", g[l][r]);
|
||
return 0;
|
||
}
|