萌新求助,过不了样例,样例输出49.8
查看原帖
萌新求助,过不了样例,样例输出49.8
576378
creation_hy楼主2022/9/2 20:36

个人感觉代码长度已经很短了

最后结果用floor()和round()都是40分

求亿能の大佬帮忙看看

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int x, y, city;
} m[405];
double INF;
int n, s, pl, a, b, t[105];
double f[405];
inline double base_dis(node x, node y)
{
    return (x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y);
}
inline double dis(node x, node y)
{
    return sqrt(base_dis(x, y)) * (x.city == y.city ? t[x.city] : pl);
}
inline node get4(node x, node y, node z, int idx)
{
    node res;
    res.city = idx;
    int xy = base_dis(x, y), yz = base_dis(y, z), xz = base_dis(x, z);
    if (xy + xz == yz)
    {
        res.x = y.x + z.x - x.x;
        res.y = y.y + z.y - x.y;
    }
    else if (xy + yz == xz)
    {
        res.x = x.x + z.x - y.x;
        res.y = x.y + z.y - y.y;
    }
    else
    {
        res.x = x.x + y.x - z.x;
        res.y = x.y + y.y - z.y;
    }
    return res;
}
queue<int> q;
double SPFA()
{
    double res = 2e9;
    int tmp;
    while (!q.empty())
    {
        tmp = q.front();
        q.pop();
        // cout << tmp.num << '\n';
        for (int i = 1; i <= s << 2; i++)
        {
            // cout << i << ' ' << f[tmp.num] << ' ' << dis(tmp, m[i]) << ' ' << f[i] << '\n';
            if (f[tmp] + dis(m[tmp], m[i]) < f[i])
            {
                if (f[i] == INF)
                    q.push(i);
                f[i] = f[tmp] + dis(m[tmp], m[i]);
                if ((b << 2) - 3 <= i && i <= b << 2)
                    res = min(res, f[i]);
                // cout << "Find " << i << ' ' << f[i] << '\n';
            }
        }
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    while (n--)
    {
        cin >> s >> pl >> a >> b;
        for (int i = 1; i <= s; i++)
        {
            cin >> m[(i << 2) - 3].x >> m[(i << 2) - 3].y >> m[(i << 2) - 2].x >> m[(i << 2) - 2].y >> m[(i << 2) - 1].x >> m[(i << 2) - 1].y >> t[i];
            m[(i << 2) - 3].city = m[(i << 2) - 2].city = m[(i << 2) - 1].city = i;
            m[i << 2] = get4(m[(i << 2) - 3], m[(i << 2) - 2], m[(i << 2) - 1], i);
        }
        q.push((a << 2) - 3);
        q.push((a << 2) - 2);
        q.push((a << 2) - 1);
        q.push(a << 2);
        memset(f, 0x42, sizeof(f));
        INF = f[1];
        f[(a << 2) - 3] = f[(a << 2) - 2] = f[(a << 2) - 1] = f[a << 2] = 0;
        cout << floor(SPFA() * 10) / 10.0;
    }
    return 0;
}

cin cout人坚决不用scanf printf

2022/9/2 20:36
加载中...