Submission #00020

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair< int64, int > Pi;
const int64 INF = 1LL << 60;
struct edge {
int to, cost;
};
vector< edge > graph[400004];
int64 min_cost[400004];
int H, W, K;
vector< Pi > X[100001], Y[100001];
int64 Dijkstra()
{
fill_n(min_cost, 400004, INF);
priority_queue< Pi, vector< Pi >, greater< Pi > > Que;
min_cost[K - 2] = 0;
Que.push(Pi(K - 2, 0));
while(!Que.empty()) {
Pi p = Que.top(); Que.pop();
if(min_cost[p.second] < p.first) continue;
if(p.second == K - 1) return(p.first);
for(auto e : graph[p.second]) {
int next = p.first + e.cost;
if(min_cost[e.to] > next) {
min_cost[e.to] = next;
Que.push(Pi(next, e.to));
}
}
}
return(-1);
}
int main()
{
cin >> W >> H >> K;
for(int i = 0; i < K; i++) {
int x, y;
cin >> x >> y;
X[x].push_back(Pi(y, i));
Y[y].push_back(Pi(x, i));
}
X[1].push_back(Pi(1, K));
Y[1].push_back(Pi(1, K));
X[W].push_back(Pi(H, K + 1));
Y[H].push_back(Pi(W, K + 1));
K += 2;
for(int i = 0; i < K - 2; i++) {
graph[i].push_back((edge){i + K, 1});
graph[i + K].push_back((edge){i, 1});
}
graph[K - 1 + K].push_back((edge){K - 1, 0});
for(int i = 0; i < 100001; i++) {
sort(X[i].begin(), X[i].end());
sort(Y[i].begin(), Y[i].end());
for(int j = 1; j < X[i].size(); ++j) {
const Pi &prev = X[i][j - 1], &curr = X[i][j];
graph[prev.second].push_back((edge){curr.second, abs(prev.first - curr.first)});
graph[curr.second].push_back((edge){prev.second, abs(prev.first - curr.first)});
}
for(int j = 1; j < Y[i].size(); ++j) {
const Pi &prev = Y[i][j - 1], &curr = Y[i][j];
graph[prev.second + K].push_back((edge){curr.second + K, abs(prev.first - curr.first)});
graph[curr.second + K].push_back((edge){prev.second + K, abs(prev.first - curr.first)});
}
}
cout << Dijkstra() << endl;
}

ステータス

項目 データ
問題 0004 - 現代的な屋敷
ユーザー名 ei1333
投稿日時 2015-12-22 14:22:33
言語 C++11
状態 Wrong Answer
得点 0
ソースコード長 2031 Byte
最大実行時間 433 ms
最大メモリ使用量 49716 KB

セット

セット 得点 Cases
1 INPUT1 0 / 20 01-*
2 INPUT2 0 / 10 02-*
3 INPUT3 0 / 20 03-*
4 INPUT4 0 / 30 04-*
5 INPUT5 0 / 20 05-*

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01-01.txt WA 328 ms 46300 KB
1
01-02.txt WA 299 ms 47084 KB
1
01-03.txt WA 302 ms 49048 KB
1
01-04.txt WA 23 ms 18160 KB
1
01-05.txt WA 350 ms 49188 KB
1
02-01.txt WA 21 ms 17916 KB
2
02-02.txt WA 25 ms 17820 KB
2
02-03.txt WA 21 ms 17864 KB
2
02-04.txt WA 24 ms 17652 KB
2
02-05.txt WA 20 ms 17696 KB
2
03-01.txt WA 25 ms 18128 KB
3
03-02.txt AC 21 ms 18068 KB
3
03-03.txt WA 21 ms 17960 KB
3
03-04.txt WA 22 ms 17932 KB
3
03-05.txt WA 22 ms 18032 KB
3
04-01.txt WA 351 ms 47440 KB
4
04-02.txt WA 362 ms 49104 KB
4
04-03.txt WA 396 ms 49584 KB
4
04-04.txt AC 392 ms 48280 KB
4
04-05.txt WA 381 ms 46948 KB
4
04-06.txt WA 272 ms 44388 KB
4
04-07.txt WA 356 ms 44652 KB
4
04-08.txt WA 353 ms 46992 KB
4
05-01.txt WA 338 ms 40180 KB
5
05-02.txt WA 382 ms 40156 KB
5
05-03.txt AC 433 ms 49716 KB
5
05-04.txt WA 317 ms 45900 KB
5
05-05.txt WA 295 ms 46880 KB
5
05-06.txt WA 353 ms 44720 KB
5
05-07.txt WA 350 ms 44668 KB
5
05-08.txt WA 369 ms 46804 KB
5