Submission #80962

ソースコード

?
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
115
116
117
#include<bits/stdc++.h>
using namespace std;
#define int long long
/*
コンテスト時間後1時間あれば行けそうだった、心安らかなり
明日の持ち物:体育館シューズ、実習服の半袖の方
明日までにやること:ハード技の復讐、キクタン
+----------------------------------------------------+
| |
| |
| このコードではr_s,p_s,r_g,p_gが逆です!! |
| |
| |
+----------------------------------------------------+
*/
double yza(int n,int x,int y){
return (sin(3.14159265358979*2*x/n)*y);
}
double xza(int n,int x,int y){
return (cos(3.14159265358979*2*x/n)*y);
}
double kyori(int n,int a,int b,int c,int d){
return hypot(xza(n,a,b)-xza(n,c,d),yza(n,a,b)-yza(n,c,d));
}
signed main(){
int n,m,k;cin>>n>>m>>k;
double dp[n+1][m+1][k+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
for(int l=0;l<=k;l++){
dp[i][j][l] = 1000;
}
}
}
int s,t,x,y;
cin>>s>>t>>x>>y;
swap(s,t);swap(x,y);
dp[s][t][0]=0;
queue<pair<pair<int,int>,int>>q;
q.push({{s,t},0});
while(!q.empty()){
int nowx=q.front().first.first;
int nowy=q.front().first.second;
int cos=q.front().second;
q.pop();
if(nowy!=m){
if(dp[nowx][nowy+1][cos] > dp[nowx][nowy][cos]+1){
dp[nowx][nowy+1][cos] = dp[nowx][nowy][cos]+1;
q.push({{nowx,nowy+1},cos});
}
}
if(nowy!=1){
if(dp[nowx][nowy-1][cos] > dp[nowx][nowy][cos]+1){
dp[nowx][nowy-1][cos] = dp[nowx][nowy][cos]+1;
q.push({{nowx,nowy-1},cos});
}
}
if(dp[(nowx+1)%n][nowy][cos] > dp[nowx][nowy][cos] + kyori(n,nowx,nowy,(nowx+1)%n,nowy)){
dp[(nowx+1)%n][nowy][cos] = dp[nowx][nowy][cos] +kyori(n,nowx,nowy,(nowx+1)%n,nowy);
q.push({{(nowx+1)%n,nowy},cos});
}
if(dp[(nowx+n-1)%n][nowy][cos] > dp[nowx][nowy][cos] + kyori(n,nowx,nowy,(nowx+n-1)%n,nowy)){
dp[(nowx+n-1)%n][nowy][cos] = dp[nowx][nowy][cos]+kyori(n,nowx,nowy,(nowx+n-1)%n,nowy);
q.push({{(nowx+n-1)%n,nowy},cos});
}
//追加する場合
if(cos<k){
if(nowy-1>=1){
if(dp[(nowx+1)%n][nowy-1][cos+1] > dp[nowx][nowy][cos] + kyori(n,nowx,nowy,(nowx+1)%n,nowy-1)){
dp[(nowx+1)%n][nowy-1][cos+1] = dp[nowx][nowy][cos] + kyori(n,nowx,nowy,(nowx+1)%n,nowy-1);
q.push({{(nowx+1)%n,nowy-1},cos+1});
}
if(dp[(nowx+n-1)%n][nowy-1][cos+1] > dp[nowx][nowy][cos] + kyori(n,nowx,nowy,(nowx+n-1)%n,nowy-1)){
dp[(nowx+n-1)%n][nowy-1][cos+1] = dp[nowx][nowy][cos] + kyori(n,nowx,nowy,(nowx+n-1)%n,nowy-1);
q.push({{(nowx+n-1)%n,nowy-1},cos+1});
}
}
if(nowy+1<=y){
if(dp[(nowx+1)%n][nowy+1][cos+1] > dp[nowx][nowy][cos] + kyori(n,nowx,nowy,(nowx+1)%n,nowy+1)){
dp[(nowx+1)%n][nowy+1][cos+1] = dp[nowx][nowy][cos] + kyori(n,nowx,nowy,(nowx+1)%n,nowy+1);
q.push({{(nowx+1)%n,nowy+1},cos+1});
}
if(dp[(nowx+n-1)%n][nowy+1][cos+1] > dp[nowx][nowy][cos] + kyori(n,nowx,nowy,(nowx+n-1)%n,nowy+1)){
dp[(nowx+n-1)%n][nowy+1][cos+1] = dp[nowx][nowy][cos] + kyori(n,nowx,nowy,(nowx+n-1)%n,nowy+1);
q.push({{(nowx+n-1)%n,nowy+1},cos+1});
}
}
if(nowy==1){
for(int i=0;i<n;i++){
if(nowx != i){
if(dp[i][nowy][cos+1] > dp[nowx][nowy][cos] + kyori(n,nowx,nowy,i,nowy)){
dp[i][nowy][cos+1] = dp[nowx][nowy][cos] + kyori(n,nowx,nowy,i,nowy);
q.push({{i,nowy},cos+1});
}
}
}
}
}
}
double ans=1000;
for(int i=0;i<=k;i++){
ans=min(ans,dp[x][y][i]);
}
printf("%.10lf\n",ans);
}

ステータス

項目 データ
問題 1543 - 蜘蛛の巣上の最短経路探索
ユーザー名 ei2326
投稿日時 2024-09-04 17:17:56
言語 C++17
状態 Accepted
得点 10
ソースコード長 4476 Byte
最大実行時間 34 ms
最大メモリ使用量 660 KB

セット

セット 得点 Cases
1 ALL 10 / 10 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 26 ms 604 KB
1
in2 AC 27 ms 444 KB
1
in3 AC 25 ms 560 KB
1
in4 AC 28 ms 532 KB
1
in5 AC 25 ms 496 KB
1
in6 AC 18 ms 596 KB
1
in7 AC 17 ms 564 KB
1
in8 AC 24 ms 660 KB
1
in9 AC 19 ms 632 KB
1
in10 AC 20 ms 572 KB
1
in11 AC 20 ms 412 KB
1
in12 AC 18 ms 508 KB
1
in13 AC 19 ms 476 KB
1
in14 AC 19 ms 572 KB
1
in15 AC 23 ms 536 KB
1
in16 AC 26 ms 492 KB
1
in17 AC 20 ms 440 KB
1
in18 AC 34 ms 516 KB
1
in19 AC 23 ms 472 KB
1
in20 AC 24 ms 540 KB
1
in21 AC 22 ms 516 KB
1
in22 AC 20 ms 480 KB
1
in23 AC 19 ms 572 KB
1
in24 AC 18 ms 536 KB
1
in25 AC 24 ms 488 KB
1
in26 AC 26 ms 560 KB
1
in27 AC 33 ms 496 KB
1