Submission #1295028
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define li long long int
#define rep(i,to) for(li i=0;i<((li)(to));i++)
#define repp(i,start,to) for(li i=(li)(start);i<((li)(to));i++)
#define pb push_back
#define sz(v) ((li)(v).size())
#define bgn(v) ((v).begin())
#define eend(v) ((v).end())
#define allof(v) (v).begin(), (v).end()
#define dodp(v,n) memset(v,(li)n,sizeof(v))
#define bit(n) (1ll<<(li)(n))
#define mp(a,b) make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;
#define INF bit(60)
#define DBGP 1
#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b) idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c) idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d) idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e) idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f) idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g) idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h) idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i) idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j) idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v) for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x) idp p2((x).F, (x).S)
#define dump(x,n) idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n) idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x) idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x) idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}
#define read2d(a,w,h) rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h) rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}
typedef pair<li, li> PI;
li board[111][111];
li dx[2][6] = {
{ -1, 0, -1, 1, -1, 0 },
{ 0, 1, -1, 1, 0, 1 }
};
li dy[2][6] = {
{ -1, -1, 0, 0, 1, 1 },
{ -1, -1, 0, 0, 1, 1 }
};
li r, c;
inline li get(PI x) {
return board[x.F][x.S];
}
map<PI, bool> visit;
inline li dijkstra(PI from, PI to) {
// {cost, pos}
priority_queue<pair<li, PI>> pq;
pq.push({0, from});
while (!pq.empty()) {
PI now = pq.top().S;
li cost_now = pq.top().F;
pq.pop();
if (now == to) {
return -cost_now;
}
visit[now] = true;
rep(i, 6) {
li ny = now.F + dy[now.F & 1][i];
li nx = now.S + dx[now.F & 1][i];
if (min(ny, nx) < 0 || ny >= r || nx >= c)continue;
PI next = {ny, nx};
if (!visit[next]) {
pq.push({cost_now - board[ny][nx], next});
//p6(now.F, now.S, "->", ny, nx, cost_now);
}
}
}
return -1;
}
int main() {
cin >> r >> c;
PI s, t;
rep(i, r) {
string ss;
cin >> ss;
rep(j, c) {
if (ss[j] == 's') {
s = {i, j};
board[i][j] = 0;
} else if (ss[j] == 't') {
t = {i, j};
board[i][j] = 0;
} else {
board[i][j] = ss[j] - '0';
}
}
}
//dump2d(board, c, r);
cout << dijkstra(s, t) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Office Ninja |
User |
ynq1242 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3691 Byte |
Status |
AC |
Exec Time |
35 ms |
Memory |
1468 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
001-sample-01.txt, 002-sample-02.txt, 003-minimum-01.txt, 004-random-01.txt, 005-random-02.txt, 006-random-03.txt, 007-random-04.txt, 008-random-05.txt, 009-random-06.txt, 010-random-07.txt, 011-random-08.txt, 012-random-09.txt, 013-random-10.txt, 014-random-11.txt, 015-random-12.txt, 016-random-13.txt, 017-random-14.txt, 018-random-15.txt, 019-random-16.txt, 020-random-17.txt, 021-random-18.txt, 022-random-19.txt, 023-random-20.txt, 024-maximum-01.txt, 025-maximum-02.txt, 026-maximum-03.txt, 027-maximum-04.txt, 999-handmade-01.txt |
Case Name |
Status |
Exec Time |
Memory |
001-sample-01.txt |
AC |
1 ms |
256 KB |
002-sample-02.txt |
AC |
1 ms |
256 KB |
003-minimum-01.txt |
AC |
1 ms |
256 KB |
004-random-01.txt |
AC |
3 ms |
384 KB |
005-random-02.txt |
AC |
4 ms |
384 KB |
006-random-03.txt |
AC |
5 ms |
384 KB |
007-random-04.txt |
AC |
1 ms |
256 KB |
008-random-05.txt |
AC |
27 ms |
896 KB |
009-random-06.txt |
AC |
1 ms |
256 KB |
010-random-07.txt |
AC |
4 ms |
384 KB |
011-random-08.txt |
AC |
2 ms |
384 KB |
012-random-09.txt |
AC |
5 ms |
384 KB |
013-random-10.txt |
AC |
2 ms |
256 KB |
014-random-11.txt |
AC |
11 ms |
512 KB |
015-random-12.txt |
AC |
2 ms |
256 KB |
016-random-13.txt |
AC |
2 ms |
384 KB |
017-random-14.txt |
AC |
13 ms |
512 KB |
018-random-15.txt |
AC |
2 ms |
384 KB |
019-random-16.txt |
AC |
11 ms |
512 KB |
020-random-17.txt |
AC |
2 ms |
256 KB |
021-random-18.txt |
AC |
3 ms |
384 KB |
022-random-19.txt |
AC |
13 ms |
640 KB |
023-random-20.txt |
AC |
1 ms |
256 KB |
024-maximum-01.txt |
AC |
13 ms |
640 KB |
025-maximum-02.txt |
AC |
35 ms |
896 KB |
026-maximum-03.txt |
AC |
21 ms |
768 KB |
027-maximum-04.txt |
AC |
8 ms |
512 KB |
999-handmade-01.txt |
AC |
7 ms |
1468 KB |