QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#502817 | #5153. Delft Distance | zhangas | WA | 8ms | 69716kb | C++14 | 2.8kb | 2024-08-03 14:43:16 | 2024-08-03 14:43:17 |
Judging History
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();
}
详细
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'