QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#502817#5153. Delft DistancezhangasWA 8ms69716kbC++142.8kb2024-08-03 14:43:162024-08-03 14:43:17

Judging History

你现在查看的是最新测评结果

  • [2024-08-03 14:43:17]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:69716kb
  • [2024-08-03 14:43:16]
  • 提交

answer

#include <bits/stdc++.h>
#define PI acos(-1)
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define PII pair<int, int>
#define int long long
using namespace std;
const int N = 2e6 + 5;
int n, m;
int id(int x, int y)
{
    return (x - 1) * (2 * m + 1) + y;
}
int hashed(int x, int y, int f)
{
    if (f == 1)
    {
        return id((x - 1) * 2 + 1, y * 2);
    }
    else if (f == 2)
    {
        return id(x * 2 + 1, y * 2);
    }
    else if (f == 3)
    {
        return id(x * 2, (y - 1) * 2 + 1);
    }
    return id(x * 2, y * 2 + 1);
}

char s[1505][1505];
vector<pair<double, int>> g[N];
void addall(int x, int y)
{
    g[hashed(x, y, 1)].push_back({10.0, hashed(x, y + 1, 1)});
    g[hashed(x, y, 1)].push_back({10.0, hashed(x, y + 1, 3)});

    g[hashed(x, y, 2)].push_back({10.0, hashed(x + 1, y + 1, 1)});
    g[hashed(x, y, 2)].push_back({10.0, hashed(x + 1, y + 1, 3)});

    g[hashed(x, y, 3)].push_back({10.0, hashed(x + 1, y, 1)});
    g[hashed(x, y, 3)].push_back({10.0, hashed(x + 1, y, 3)});

    g[hashed(x, y, 4)].push_back({10.0, hashed(x + 1, y + 1, 1)});
    g[hashed(x, y, 4)].push_back({10.0, hashed(x + 1, y + 1, 3)});
}
void addo(int x, int y)
{
    double L = PI * 5.0 / 2.0;
    g[hashed(x, y, 1)].push_back({L, hashed(x, y, 4)});
    g[hashed(x, y, 3)].push_back({L, hashed(x, y, 2)});
}

int st[N];
double dist[N];
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
double dijkstra()
{
    for (int i = 0; i < N; ++i)
        dist[i] = 2e9;

    g[id(0, 0)].push_back({5.0, hashed(1, 1, 1)});
    g[id(0, 0)].push_back({5.0, hashed(1, 1, 3)});
    dist[id(0, 0)] = 0;
    q.push({0.0, id(0, 0)});

    while (q.size())
    {
        pair<double, int> t = q.top();
        q.pop();
        double distance = t.first;
        int u = t.second;
        if (st[u])
            continue;
        st[u] = 1;
        for (int i = 0; i < g[u].size(); ++i)
        {
            int j = g[u][i].second;
            double d = g[u][i].first;
            if (dist[j] > dist[u] + d)
            {
                dist[j] = dist[u] + d;
                if (!st[j])
                {
                    q.push({dist[j], j});
                }
            }
        }
    }
    return min(dist[hashed(n, m, 2)], dist[hashed(n, m, 4)]) + 5.0;
}

void solves()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> s[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            addall(i, j);
            if (s[i][j] == 'O')
                addo(i, j);
        }
    printf("%.10lf", dijkstra());
}

signed main()
{
    IOS;
    int T = 1;
    // cin >> T;
    while (T--)
        solves();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 69716kb

input:

3 5
XOOXO
OXOXO
XXXXO

output:

2000000005.0000000000

result:

wrong answer 1st numbers differ - expected: '71.4159265', found: '2000000005.0000000', error = '28004956.7455895'