QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#501224 | #5153. Delft Distance | xixu | RE | 3ms | 5376kb | C++20 | 4.4kb | 2024-08-02 15:47:54 | 2024-08-02 15:47:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
typedef pair<int , int> PII;
const int N = 1e5 + 10 , inf = 0x3f3f3f3f;
const double PI = 3.1415926535;
typedef pair<int, int> PII;
typedef pair<double , pair<int , int>> PL;
int n , m; // 点的数量
PII e[N];
int ne[N];
double w[N];
int idx; // 邻接表存储所有边
map<PII , int> h;
map<PII , double> dist;
map<PII , bool> st;
// 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];
h[a] = idx ++;
}
// 求1号点到n号点的最短距离,如果不存在,则返回-1
double dijkstra()
{
// memset(dist, 0x3f, sizeof dist);
for(int i = 1; i <= 2 * n + 1; i ++)
{
for(int j = 1; j <= 2 * m + 1; 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]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
PII j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
return dist[{2 * n + 1 , 2 * m + 1}];
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= 2 * n + 1; i ++)
{
for(int j = 1; j <= 2 * m + 1; 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);
ios::sync_with_stdio(false);
int t = 1;
// cin >> t;
while(t --)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3980kb
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: 0ms
memory: 3744kb
input:
1 4 XOOX
output:
45.707963267500
result:
ok found '45.7079633', expected '45.7079633', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4040kb
input:
1 1 X
output:
20.000000000000
result:
ok found '20.0000000', expected '20.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4032kb
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: 3808kb
input:
1 3 XOO
output:
35.707963267500
result:
ok found '35.7079633', expected '35.7079633', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
1 5 OXOOO
output:
55.707963267500
result:
ok found '55.7079633', expected '55.7079633', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4092kb
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: 0ms
memory: 3888kb
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: 3804kb
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: 3948kb
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: 2ms
memory: 4192kb
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: 3ms
memory: 5376kb
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
Runtime Error
input:
329 527 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...