Submission #71984
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include <bits/stdc++.h> #include <iomanip> using namespace std; int n, m, k, a, b, c, d; double p, z, ans; double dp[21][11][11]; struct sp{ int u, v, w; }; queue<sp> Q; double dist( int x, int y, int z, int w){ return sqrt (x * x + z * z - 2 * x * z * cos ((y - w) * p * 2 / n)); } int main(){ cin >> n >> m >> k >> a >> b >> c >> d; if (b > d) swap(b, d); if (d - b > n / 2) d = n - d + b; else d = d - b; b = 0; p = acos (-1); for ( int i = 1; i <= m; i++){ for ( int j = 0; j <= n / 2; j++){ for ( int l = 0; l <= k; l++){ dp[i][j][l] = 1e9; } } } dp[a][b][0] = 0; sp s1 = {a, b, 0}; Q.push(s1); while (!Q.empty()){ sp st = Q.front(); Q.pop(); int u = st.u, v = st.v, w = st.w; if (u > 1){ if (dp[u - 1][v][w] > dp[u][v][w] + 1){ dp[u - 1][v][w] = dp[u][v][w] + 1; sp s2 = {u - 1, v, w}; Q.push(s2); } if (w < k){ z = dist(u, v, u - 1, v + 1); if (dp[u - 1][v + 1][w + 1] > dp[u][v][w] + z){ dp[u - 1][v + 1][w + 1] = dp[u][v][w] + z; sp s2 = {u - 1, v + 1, w + 1}; Q.push(s2); } } } if (u < m){ if (dp[u + 1][v][w] > dp[u][v][w] + 1){ dp[u + 1][v][w] = dp[u][v][w] + 1; sp s2 = {u + 1, v, w}; Q.push(s2); } if (w < k){ z = dist(u, v, u + 1, v + 1); if (dp[u + 1][v + 1][w + 1] > dp[u][v][w] + z){ dp[u + 1][v + 1][w + 1] = dp[u][v][w] + z; sp s2 = {u + 1, v + 1, w + 1}; Q.push(s2); } } } if (v < d){ z = dist(u, v, u, v + 1); if (dp[u][v + 1][w] > dp[u][v][w] + z){ dp[u][v + 1][w] = dp[u][v][w] + z; sp s2 = {u, v + 1, w}; Q.push(s2); } if (u == 1 && w < k){ for ( int x = v + 1; x <= d; x++){ z = dist(u, v, u, x); if (dp[u][x][w + 1] > dp[u][v][w] + z){ dp[u][x][w + 1] = dp[u][v][w] + z; sp s2 = {u, x, w + 1}; Q.push(s2); } } } } } ans = 1e9; for ( int i = 0; i <= k; i++) ans = min(ans, dp[c][d][i]); cout << setprecision(10) << ans << endl; } |
ステータス
項目 | データ |
---|---|
問題 | 1543 - 蜘蛛の巣上の最短経路探索 |
ユーザー名 | syoribu |
投稿日時 | 2022-08-30 09:36:28 |
言語 | C++17 |
状態 | Accepted |
得点 | 10 |
ソースコード長 | 2915 Byte |
最大実行時間 | 31 ms |
最大メモリ使用量 | 780 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 10 / 10 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
in1 | AC | 23 ms | 476 KB |
1
|
in2 | AC | 26 ms | 556 KB |
1
|
in3 | AC | 24 ms | 644 KB |
1
|
in4 | AC | 18 ms | 600 KB |
1
|
in5 | AC | 25 ms | 692 KB |
1
|
in6 | AC | 21 ms | 660 KB |
1
|
in7 | AC | 24 ms | 624 KB |
1
|
in8 | AC | 24 ms | 460 KB |
1
|
in9 | AC | 22 ms | 552 KB |
1
|
in10 | AC | 18 ms | 444 KB |
1
|
in11 | AC | 21 ms | 388 KB |
1
|
in12 | AC | 31 ms | 592 KB |
1
|
in13 | AC | 24 ms | 536 KB |
1
|
in14 | AC | 20 ms | 356 KB |
1
|
in15 | AC | 16 ms | 428 KB |
1
|
in16 | AC | 21 ms | 500 KB |
1
|
in17 | AC | 23 ms | 696 KB |
1
|
in18 | AC | 22 ms | 644 KB |
1
|
in19 | AC | 23 ms | 588 KB |
1
|
in20 | AC | 20 ms | 644 KB |
1
|
in21 | AC | 20 ms | 484 KB |
1
|
in22 | AC | 21 ms | 704 KB |
1
|
in23 | AC | 20 ms | 780 KB |
1
|
in24 | AC | 23 ms | 724 KB |
1
|
in25 | AC | 25 ms | 540 KB |
1
|
in26 | AC | 21 ms | 616 KB |
1
|
in27 | AC | 20 ms | 696 KB |
1
|