QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226846 | #5153. Delft Distance | Fyind# | WA | 0ms | 3880kb | C++23 | 2.6kb | 2023-10-26 17:13:39 | 2023-10-26 17:13:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long double ll;
const int maxn = 5e5 + 5;
struct Dijkstra {
int n=0;
vector<vector<pair<int, ll>>> G;
vector<ll> d;
Dijkstra() : G(1),d(1) {}
void addedge(int x, int y, ll val) {
n = max(x,y);
while (sz(d)-1 <= n) {
d.resize(sz(d)<<1);
G.resize(sz(G)<<1);
}
G[x].push_back({y, val});
G[y].push_back({x, val});
}
void calc(int s) {
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> Q;
vector<bool> done(n+1);
d.assign(n+1, 1e18); d[s] = 0;
Q.push({d[s], s});
while(!Q.empty()) {
int x = Q.top().second; Q.pop();
if (done[x]) continue; else done[x] = true;
for (auto [v, len] : G[x]) if (d[v] > d[x] + len) {
d[v] = d[x] + len;
Q.push({d[v], v});
}
}
}
};
int n, m;
int getid(int x,int y) {
return x*(2*m+1) + y;
}
char A[710][710];
Dijkstra dij;
const long double lenc = acos((ll)-1)*5/2;
void add(int x4,int y4, char c) {
x4 *= 2, y4 *= 2;
int x1 = x4-2,y1 = y4-2;
int x2 = x4-2, y2 = y4;
int x3 = x4, y3 = y4-2;
int x12 = (x1+x2)/2, y12 = (y1+y2)/2;
int x13 = (x1+x3)/2, y13 = (y1+y3)/2;
int x34 = (x3+x4)/2, y34 = (y3+y4)/2;
int x24 = (x2+x4)/2, y24 = (y2+y4)/2;
dij.addedge(getid(x1,y1),getid(x12,y12), 5);
dij.addedge(getid(x12,y12),getid(x2,y2), 5);
dij.addedge(getid(x1,y1),getid(x13,y13), 5);
dij.addedge(getid(x13,y13),getid(x3,y3), 5);
dij.addedge(getid(x3,y3),getid(x34,y34), 5);
dij.addedge(getid(x34,y34),getid(x4,y4), 5);
dij.addedge(getid(x2,y2),getid(x24,y24), 5);
dij.addedge(getid(x24,y24),getid(x4,y4), 5);
if (c == 'O') {
dij.addedge(getid(x13,y13),getid(x12,y12), lenc);
dij.addedge(getid(x13,y13),getid(x34,y34), lenc);
dij.addedge(getid(x34,y34),getid(x24,y24), lenc);
dij.addedge(getid(x12,y12),getid(x24,y24), lenc);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1;i <= n; ++i) {
for (int j = 1;j <= m; ++j) {
cin >> A[i][j];
}
}
for (int i = 1;i <= n; ++i) {
for (int j = 1;j <= m; ++j) {
add(i,j,A[i][j]);
}
}
dij.calc(getid(0,0));
cout << fixed << setprecision(6) << dij.d[getid(n*2,m*2)] << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3880kb
input:
3 5 XOOXO OXOXO XXXXO
output:
0.000000
result:
wrong answer 1st numbers differ - expected: '71.4159265', found: '0.0000000', error = '1.0000000'