QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#140843#5153. Delft DistanceAs3b_team_f_masr#WA 1ms40636kbC++142.6kb2023-08-16 21:14:342023-08-16 21:14:35

Judging History

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

  • [2023-08-16 21:14:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:40636kb
  • [2023-08-16 21:14:34]
  • 提交

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;
}

詳細信息

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'