QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#140843 | #5153. Delft Distance | As3b_team_f_masr# | WA | 1ms | 40636kb | C++14 | 2.6kb | 2023-08-16 21:14:34 | 2023-08-16 21:14:35 |
Judging History
answer
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0, 0, 1, -1, 1};
int dj[] = {0, 1, 0, -1, -1, 0, 1, -1};
const ll oo = 1e18, MOD = 1e9 + 7;
const int N = 705, M = 30005;
#define EPS 1e-9
int n, m;
double d[N][N][3];
char c[N][N];
vector<pair<pair<int, int>, pair<int, double>>> v[N][N][3];
double dijkstra() {
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int k = 0; k < 3; k++) d[i][j][k] = 1000000000;
priority_queue<pair<pair<double,int>,pair<int,int>>>q;
d[1][1][0]=0;
q.push({{0,0},{1,1}});
while(!q.empty()){
auto k=q.top();
q.pop();
int x=k.second.first,y=k.second.second;
double dis=-k.first.first;
int op=k.first.second;
cout<<x<<" "<<y<<" "<<op<<endl;
if(dis>d[x][y][op]) continue;
for(auto z:v[x][y][op]){
if(d[z.first.first][z.first.second][z.second.first]>z.second.second+d[x][y][op]){
d[z.first.first][z.first.second][z.second.first]=z.second.second+d[x][y][op];
q.push({{-d[z.first.first][z.first.second][z.second.first],z.second.first},{z.first.first,z.first.second}});
}
}
}
return d[n][m][0];
}
int main() {
//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//freopen("output.txt", "w", stdout);
double dis=M_PI*2.5;
cin >> n >> m;
for (int i = 1; i <= n+1; i++) {
for (int j = 1; j <= m+1; j++) {
if(i<=n && j<=m) cin >> c[i][j];
else c[i][j]='x';
v[i][j][0].push_back({{i, j}, {1,5}});
v[i][j][0].push_back({{i, j}, {2,5}});
v[i][j][1].push_back({{i, j},{0,5}});
v[i][j][2].push_back({{i, j}, {0,5}});
v[i][j][1].push_back({{i, j + 1}, {0,5}});
v[i][j+1][0].push_back({{i, j}, {1,5}});
v[i][j][2].push_back({{i + 1, j}, {0,5}});
v[i+1][j][0].push_back({{i, j}, {2,5}});
if (c[i][j] == 'O') {
v[i][j][1].push_back({{i, j}, {2,dis}});
v[i][j][2].push_back({{i, j}, {1,dis}});
v[i][j][1].push_back({{i, j + 1}, {2,dis}});
v[i][j+1][2].push_back({{i, j}, {1,dis}});
v[i][j][2].push_back({{i + 1, j}, {1,dis}});
v[i+1][j][1].push_back({{i, j}, {2,dis}});
v[i][j+1][2].push_back({{i + 1, j}, {1,dis}});
v[i+1][j][1].push_back({{i, j+1}, {2,dis}});
}
}
}
n++,m++;
cout << fixed<<setprecision(8)<<dijkstra();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 40636kb
input:
3 5 XOOXO OXOXO XXXXO
output:
1 1 0 1 1 2 1 1 1 2 1 0 1 2 0 2 1 2 1 2 2 2 1 1 1 2 1 3 1 0 2 2 0 1 3 0 2 2 2 1 3 2 3 1 1 2 2 1 3 1 2 1 3 1 3 2 0 2 3 0 4 1 0 1 4 0 2 3 1 3 2 2 2 3 2 1 4 2 3 2 1 4 1 2 4 1 1 1 4 1 2 4 0 4 2 0 3 3 0 2 4 2 1 5 0 3 3 1 2 4 1 4 2 2 3 3 2 4 2 1 3 4 0 1 5 2 1 5 1 2 5 0 4 3 0 3 4 2 3 4 1 1 6 0 2 5 2 2 5 1 ...
result:
wrong answer 1st numbers differ - expected: '71.4159265', found: '1.0000000', error = '0.9859975'