#include<bits/stdc++.h>
#include "cyberland.h"
using namespace std;
using pid = pair<int, double>;
using tp = tuple<double, int, int, int>;
const int N = 1e5 + 5, K = 75;
double d[N][K][2], ans;
vector<pid> v[N];
bool f[N][K][2];
double solve(int n, int m, int k, int h, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
k = min(k, 67), ans = DBL_MAX;
priority_queue<tp, vector<tp>, greater<tp>> q;
for (int i = 0; i <= n; i++) v[i].clear();
for (int i = 0; i < m; i++) v[x[i]].emplace_back(y[i], c[i]), v[y[i]].emplace_back(x[i], c[i]);
for (int i = 0; i <= n; i++) for (int j = 0; j <= k; j++) d[i][j][0] = d[i][j][1] = 1e11, f[i][j][0] = f[i][j][1] = 0;
q.emplace(d[h][0][0] = 0, h, 0, 0);
while (!q.empty()) {
auto [nd, nn, nsa, nsb] = q.top(); q.pop();
if (f[nn][nsa][nsb]) continue; f[nn][nsa][nsb] = 1;
for (auto &[tn, td]: v[nn]) {
double nds = nd + (nsb ? 0 : td / pow((double) 2, nsa));
if (d[tn][nsa][nsb] > nds) q.emplace(d[tn][nsa][nsb] = nds, tn, nsa, nsb);
}
if (!arr[nn]) for (auto &[tn, td]: v[nn]) if (d[tn][nsa][!nsb] > nd) q.emplace(d[tn][nsa][!nsb] = nd, tn, nsa, !nsb);
if (nsa < k && arr[nn] == 2) {
for (auto &[tn, td]: v[nn]) {
double nds = nd + (nsb ? 0 : td / pow((double) 2, nsa + 1));
if (d[tn][nsa][nsb] > nds) q.emplace(d[tn][nsa][nsb] = nds, tn, nsa + 1, nsb);
}
}
}
for (int i = 0; i <= k; i++) for (int j = 0; j < 2; j++) ans = min(ans, d[0][i][j]);
return (ans == 1e11 ? -1 : ans);
}
Compilation message
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:22:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
22 | if (f[nn][nsa][nsb]) continue; f[nn][nsa][nsb] = 1;
| ^~
cyberland.cpp:22:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
22 | if (f[nn][nsa][nsb]) continue; f[nn][nsa][nsb] = 1;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
25 ms |
2892 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
4268 KB |
Correct. |
2 |
Correct |
28 ms |
4320 KB |
Correct. |
3 |
Correct |
28 ms |
4216 KB |
Correct. |
4 |
Correct |
26 ms |
4276 KB |
Correct. |
5 |
Correct |
26 ms |
4256 KB |
Correct. |
6 |
Correct |
28 ms |
16588 KB |
Correct. |
7 |
Correct |
35 ms |
16368 KB |
Correct. |
8 |
Correct |
25 ms |
30288 KB |
Correct. |
9 |
Correct |
23 ms |
3004 KB |
Correct. |
10 |
Correct |
28 ms |
2996 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
37 ms |
4284 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1678 ms |
109008 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
4308 KB |
Correct. |
2 |
Correct |
30 ms |
4296 KB |
Correct. |
3 |
Correct |
24 ms |
4300 KB |
Correct. |
4 |
Correct |
35 ms |
16936 KB |
Correct. |
5 |
Correct |
21 ms |
2924 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
34 ms |
4332 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
407 ms |
5632 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
763 ms |
6832 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |