QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226846#5153. Delft DistanceFyind#WA 0ms3880kbC++232.6kb2023-10-26 17:13:392023-10-26 17:13:39

Judging History

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

  • [2023-10-26 17:13:39]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3880kb
  • [2023-10-26 17:13:39]
  • 提交

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'