Submission #58450

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define read cin >>
#define echo cout <<
#define fin << '\n'
#define _ << ' ' <<
#define in :
#define var auto&&
#define let const auto
int getX(int num){
if(num == 3 || num == 6 || num == 9){
return 0;
}
else if(num == 2 || num == 5 || num == 8){
return 1;
}
return 2;
}
int getY(int num){
if(num == 0){
return 0;
}
else if(num <= 3 && num >= 1){
return 1;
}
else if(num <= 6 && num >= 4){
return 2;
}
return 3;
}
struct DijkstraData {
int pos, mod, cost;
bool operator < ( const DijkstraData &tar ) const {
return cost < tar.cost;
}
bool operator > ( const DijkstraData &tar ) const {
return cost > tar.cost;
}
};
vector<pair<int, int> > g[100100];
int dist[11][100100];
int m, r;
int dijkstra ( int start, int goal ) {
priority_queue<DijkstraData, vector<DijkstraData>, greater<DijkstraData> > p;
for ( int i = 0; i < 11; i++ ) {
for ( int j = 0; j < 100100; j++ ) {
dist[i][j] = 0x3f3f3f3f;
}
}
dist[0][start] = 0;
p.push((DijkstraData){start, 0, 0});
while ( !p.empty() ) {
DijkstraData now = p.top();
p.pop();
int cost = now.cost;
int mod = now.mod;
int pos = now.pos;
if ( dist[pos][mod] != cost ) continue;
for ( int i = 0; i < (int)g[pos].size(); i++ ) {
int next = g[pos][i].first;
int ncst = g[pos][i].second + cost + 1;
int nmod = ( mod * 10 + next ) % m;
if ( ncst < dist[next][nmod] ) {
dist[next][nmod] = ncst;
p.push((DijkstraData){next, nmod, ncst});
}
}
}
int ans = 0x3f3f3f3f;
for ( int i = 0; i < 10; i++ ) {
ans = min ( ans, dist[i][goal] );
}
return ans;
}
void build_graph ( ) {
for ( int i = 0; i < 10; i++ ) {
for ( int j = 0; j < 10; j++ ) {
int zettaichi = abs(getX(i)-getX(j))
+ abs(getY(i)-getY(j));
g[i].push_back(make_pair(j, zettaichi));
}
}
}
signed main ( ) {
read m >> r;
build_graph();
echo dijkstra(0, r) fin;
return 0;
}

ステータス

項目 データ
問題 1268 - テンキー (Tenkey)
ユーザー名 r1825
投稿日時 2020-02-04 17:09:57
言語 C++14
状態 Accepted
得点 100
ソースコード長 2395 Byte
最大実行時間 358 ms
最大メモリ使用量 37664 KB

セット

セット 得点 Cases
1 Subtask1 30 / 30 sample*, 01*
2 Subtask2 70 / 70 sample*, 01*, 02*

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01-01.txt AC 55 ms 13140 KB
1
2
01-02.txt AC 40 ms 13188 KB
1
2
01-03.txt AC 47 ms 13112 KB
1
2
01-04.txt AC 49 ms 13040 KB
1
2
01-05.txt AC 45 ms 13096 KB
1
2
01-06.txt AC 42 ms 13148 KB
1
2
01-07.txt AC 43 ms 13196 KB
1
2
01-08.txt AC 52 ms 13120 KB
1
2
01-09.txt AC 53 ms 13168 KB
1
2
01-10.txt AC 41 ms 13088 KB
1
2
01-11.txt AC 44 ms 13140 KB
1
2
01-12.txt AC 42 ms 13192 KB
1
2
01-13.txt AC 49 ms 13112 KB
1
2
01-14.txt AC 48 ms 13168 KB
1
2
02-01.txt AC 26 ms 11436 KB
2
02-02.txt AC 23 ms 12040 KB
2
02-03.txt AC 21 ms 11660 KB
2
02-04.txt AC 26 ms 11524 KB
2
02-05.txt AC 21 ms 11728 KB
2
02-06.txt AC 23 ms 11628 KB
2
02-07.txt AC 55 ms 15844 KB
2
02-08.txt AC 183 ms 37164 KB
2
02-09.txt AC 86 ms 19092 KB
2
02-10.txt AC 209 ms 36816 KB
2
02-11.txt AC 68 ms 18732 KB
2
02-12.txt AC 29 ms 12488 KB
2
02-13.txt AC 319 ms 36872 KB
2
02-14.txt AC 289 ms 37208 KB
2
02-15.txt AC 41 ms 15372 KB
2
02-16.txt AC 157 ms 25092 KB
2
02-17.txt AC 51 ms 16320 KB
2
02-18.txt AC 118 ms 24544 KB
2
02-19.txt AC 215 ms 24900 KB
2
02-20.txt AC 357 ms 36868 KB
2
02-21.txt AC 182 ms 24136 KB
2
02-22.txt AC 20 ms 11968 KB
2
02-23.txt AC 21 ms 12000 KB
2
02-24.txt AC 186 ms 25044 KB
2
02-25.txt AC 358 ms 36300 KB
2
02-26.txt AC 334 ms 36932 KB
2
02-27.txt AC 174 ms 24412 KB
2
02-28.txt AC 211 ms 24788 KB
2
02-29.txt AC 341 ms 37664 KB
2
02-30.txt AC 169 ms 25268 KB
2
02-31.txt AC 47 ms 14836 KB
2
02-32.txt AC 181 ms 25168 KB
2
02-33.txt AC 44 ms 13208 KB
2
02-34.txt AC 52 ms 13244 KB
2
02-35.txt AC 45 ms 13276 KB
2
sample-01.txt AC 45 ms 13288 KB
1
2
sample-02.txt AC 26 ms 11680 KB
1
2