数据下载后发现太大了调不了,代码如下:
#include <iostream>
#include <iomanip>
#include <cstring>
#include <vector>
#include <cmath>
const int N = 1005;
bool vis[N];
int n,m,s,t;
std::vector<int> p[N];
struct pos{int x,y;}a[N];
double ans = 1e1000,nowDis = 0;
int sq(int a){return a * a;}
double dist(pos a,pos b){return sqrt(sq(a.x - b.x) + sq(a.y - b.y));}
void dfs(int x){
if (x == t){
ans = std::min(ans,nowDis);
return;
}
for (int i = 0;i < p[x].size();i++)
if (!vis[p[x][i]]){
vis[p[x][i]] = true;
nowDis += dist(a[x],a[p[x][i]]);
dfs(p[x][i]);
nowDis -= dist(a[x],a[p[x][i]]);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("P1774.in","r",stdin);
#endif
std::cin.tie(0)->sync_with_stdio(0);
std::cin >> n;
for (int i = 1;i <= n;i++) std::cin >> a[i].x >> a[i].y;
std::cin >> m;
for (int i = 1;i <= m;i++){
int I,J;
std::cin >> I >> J;
p[I].push_back(J);
p[J].push_back(I);
}
std::cin >> s >> t;
memset(vis,false,sizeof(vis));
vis[s] = true;
dfs(s);
std::cout << std::fixed << std::setprecision(2) << ans << '\n';
return 0;
}