60pts,WA on #1,#3(悬关)
查看原帖
60pts,WA on #1,#3(悬关)
1074084
asd890123楼主2024/7/3 20:50

数据下载后发现太大了调不了,代码如下:

#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;
}
2024/7/3 20:50
加载中...