QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#501272#5153. Delft DistancexixuWA 2ms20840kbC++204.5kb2024-08-02 16:17:072024-08-02 16:17:08

Judging History

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

  • [2024-08-02 16:17:08]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:20840kb
  • [2024-08-02 16:17:07]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define int short

typedef long long ll;
typedef pair<int , int> PII;


const int M = 2e7 + 10 , inf = 0x3f3f3f3f , N = 1500;
const double PI = 3.1415926535;


typedef pair<int, int> PII;
typedef pair<double , pair<int , int>> PL;

int n , m;      // 点的数量
PII e[20000010];
int ne[20000010];
double w[20000010];
int idx;       // 邻接表存储所有边
int h[1500][1500];
double dist[1500][1500];
bool st[1500][1500];
// double dist[N];        // 存储所有点到1号点的距离
// bool st[N];     // 存储每个点的最短距离是否已确定

void add(PII a , PII b , double c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a.first][a.second];
    h[a.first][a.second] = idx ++;
}

// 求1号点到n号点的最短距离,如果不存在,则返回-1
double dijkstra()
{
    // memset(dist, 0x3f, sizeof dist);
    for(int i = 1; i <= 2 * n + 2; i ++)
    {
        for(int j = 1; j <= 2 * m + 2; j ++)
        {
            dist[i][j] = inf;
        }
    }
    dist[1][1] = 0;

    priority_queue<PL, vector<PL>, greater<PL>> heap;
    heap.push({0, {1 , 1}});      // first存储距离,second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        // cout << t.second.first << ' ' << t.second.second << '\n';

        PII ver = t.second;
        double distance = t.first;

        if (st[ver.first][ver.second]) continue;
        st[ver.first][ver.second] = true;

        for (int i = h[ver.first][ver.second]; i != -1; i = ne[i])
        {
            PII j = e[i];
            if (dist[j.first][j.second] > distance + w[i])
            {
                dist[j.first][j.second] = distance + w[i];
                heap.push({dist[j.first][j.second], j});
            }
        }
    }

    return dist[2 * n + 1][2 * m + 1];
}





void solve()
{
    
    cin >> n >> m;

    for(int i = 0; i <= 2 * n + 2; i ++)
    {
        for(int j = 0; j <= 2 * m + 2; j ++)
        {
            h[i][j] = -1;
        }
    }

    for(int i = 1; i < 2 * n; i += 2)
    {
        for(int j = 1; j < 2 * m; j += 2)
        {
            // cout << i << ' ' << j << '\n';
            char c;
            cin >> c;
            if(c == 'X')
            {
                add({i , j} , {i , j + 2} , 10);
                add({i , j + 2} , {i , j} , 10);

                add({i , j} , {i + 2 , j} , 10);
                add({i + 2 , j} , {i , j} , 10);

                add({i , j + 2} , {i + 2 , j + 2} , 10);
                add({i + 2 , j + 2} , {i , j + 2} , 10);

                add({i + 2 , j} , {i + 2 , j + 2} , 10);
                add({i + 2 , j + 2} , {i + 2 , j} , 10);
            }
            else
            {
                add({i ,j} , {i + 1 , j} , 5);
                add({i + 1 , j} , {i , j} , 5);

                add({i + 1 , j} , {i + 2 , j} , 5);
                add({i + 2 , j} , {i + 1 , j} , 5);

                add({i + 2 , j} , {i + 2 , j + 1} , 5);
                add({i + 2 , j + 1} , {i + 2 , j} , 5);

                add({i + 2 , j + 1} , {i + 2 , j + 2} , 5);
                add({i + 2 , j + 2} , {i + 2 , j + 1} , 5);

                add({i + 2 , j + 2} , {i + 1 , j + 2} , 5);
                add({i + 1 , j + 2} , {i + 2 , j + 2} , 5);

                add({i + 1 , j + 2} ,{i , j + 2} , 5);
                add({i ,j + 2} , {i + 1 , j + 2} , 5);

                add({i , j + 2} , {i , j + 1} , 5);
                add({i , j + 1} , {i , j + 2} , 5);

                add({i , j + 1} , {i , j} , 5);
                add({i , j} , {i , j + 1} , 5);

                add({i + 1 , j} , {i , j + 1} , 5 * PI / 2);
                add({i , j + 1} , {i + 1 , j} , 5 * PI / 2);

                // cout << 5 * PI / 2 << '\n';
                add({i , j + 1} , {i + 1 , j + 2} , 5 * PI / 2);
                add({i + 1 , j + 2} , {i , j + 1} , 5 * PI / 2);

                add({i + 1 , j + 2} , {i + 2 , j + 1} , 5 * PI / 2);
                add({i + 2 , j + 1} , {i + 1 , j + 2} , 5 * PI / 2);

                add({i + 2 , j + 1} , {i + 1 , j} , 5 * PI / 2);
                add({i + 1 , j} , {i + 2 , j + 1} , 5 * PI / 2);
            }

        }
    }

    cout << fixed << setprecision(12) << dijkstra() << '\n';


}



signed main()
{
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while(t --)
    {
        solve();
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 12216kb

input:

3 5
XOOXO
OXOXO
XXXXO

output:

71.415926535000

result:

ok found '71.4159265', expected '71.4159265', error '0.0000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 12052kb

input:

1 4
XOOX

output:

45.707963267500

result:

ok found '45.7079633', expected '45.7079633', error '0.0000000'

Test #3:

score: 0
Accepted
time: 2ms
memory: 12080kb

input:

1 1
X

output:

20.000000000000

result:

ok found '20.0000000', expected '20.0000000', error '0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 12080kb

input:

1 1
O

output:

17.853981633750

result:

ok found '17.8539816', expected '17.8539816', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 12152kb

input:

1 3
XOO

output:

35.707963267500

result:

ok found '35.7079633', expected '35.7079633', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 12012kb

input:

1 5
OXOOO

output:

55.707963267500

result:

ok found '55.7079633', expected '55.7079633', error '0.0000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 12020kb

input:

6 10
XXXXXOOOOX
XXOOOOOOOO
XXXOXOOXOX
OXOXOXXOOX
OOXXOXXXXO
OXOXXOOXOO

output:

142.831853070000

result:

ok found '142.8318531', expected '142.8318531', error '0.0000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 11988kb

input:

1 2
XX

output:

30.000000000000

result:

ok found '30.0000000', expected '30.0000000', error '0.0000000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 14056kb

input:

10 1
X
X
X
O
O
O
X
O
O
X

output:

105.707963267500

result:

ok found '105.7079633', expected '105.7079633', error '0.0000000'

Test #10:

score: 0
Accepted
time: 1ms
memory: 12088kb

input:

18 6
OOOOOO
OOOOOO
XOOOOO
OOOOXO
OOOXOO
OOOOOO
OOOOOO
OOOOOO
OOOOOX
OOOOOO
OOOXOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO

output:

214.247779605000

result:

ok found '214.2477796', expected '214.2477796', error '0.0000000'

Test #11:

score: 0
Accepted
time: 1ms
memory: 12364kb

input:

40 9
OOOOXOXXX
XOXXXOXXO
OXOXXXXXO
OXOXXXOXX
XXXXOXOXX
XXOOXOXXX
XOOXOXXXX
XOXXOOXOX
OXXOOOOXX
XXOOOXXOO
OXOOXOXXX
OOOOOXOOO
OXXXXXXXO
OOOOOOOXX
OOOXXXOOX
OXOXXOOOO
OOOOXOXOO
OXOXOOOXO
OXXOOXXXO
OXOOXOOXO
XXXOXOXOO
XXOOOXOOX
OOXXOOXOO
XOOXXXXOX
OXXXXOOOO
OXOOOOXOX
XXOXXXOOO
OOXOOOXXX
OXOOOOXOO
OXOOO...

output:

453.517687773750

result:

ok found '453.5176878', expected '453.5176878', error '0.0000000'

Test #12:

score: 0
Accepted
time: 2ms
memory: 14456kb

input:

41 50
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXO
XXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXX
XXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXX...

output:

873.517687773750

result:

ok found '873.5176878', expected '873.5176878', error '0.0000000'

Test #13:

score: -100
Wrong Answer
time: 0ms
memory: 20840kb

input:

329 527
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

220.000000000000

result:

wrong answer 1st numbers differ - expected: '8560.0000000', found: '220.0000000', error = '0.9742991'