結果

問題 No.971 いたずらっ子
ユーザー roarisroaris
提出日時 2020-01-17 21:57:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,248 bytes
コンパイル時間 1,614 ms
コンパイル使用メモリ 172,696 KB
実行使用メモリ 24,192 KB
最終ジャッジ日時 2024-06-25 19:51:35
合計ジャッジ時間 6,939 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 11 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
#define INF 1000000
int H, W;
char a[2100][2100];
int dist[2100][2100];
void dijkstra() {
for (int i=0; i<H; i++) for (int j=0; j<W; j++) dist[i][j] = INF;
dist[0][0] = 0;
priority_queue<P, vector<P>, greater<P>> pq;
pq.push(P(0, 0));
while (pq.size()) {
P p = pq.top(); pq.pop();
int d = p.first;
int v = p.second;
int x = v/W, y = v%W;
if (dist[x][y]<d) continue;
if (x<H-1) {
int w;
if (a[x+1][y]=='k') w = x+y+2;
else w = 1;
if (dist[x+1][y]>dist[x][y]+w) {
dist[x+1][y] = dist[x][y]+w;
pq.push(P(dist[x+1][y], W*(x+1)+y));
}
}
if (y<W-1) {
int w;
if (a[x][y+1]=='k') w = x+y+2;
else w = 1;
if (dist[x][y+1]>dist[x][y]+w) {
dist[x][y+1] = dist[x][y]+w;
pq.push(P(dist[x][y+1], W*x+y+1));
}
}
}
}
int main() {
cin >> H >> W;
for (int i=0; i<H; i++) for (int j=0; j<W; j++) cin >> a[i][j];
dijkstra();
cout << dist[H-1][W-1] << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0