Submission #00050

ソースコード

?
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
#include<bits/stdc++.h>
#define LLINF (1LL<<60)
#define INF (1<<29)
#define F first
#define S second
#define ALL(a) a.begin(),a.end()
using namespace std;
typedef pair<long long,long long>P;
typedef pair<long long,P> lP;
typedef struct{
vector<P> to;
vector<P> toskip;
long long min[100];
long long level;
}Edge;
long long p=0;
Edge edge[2000];
vector<lP> stone[200];
long long n,m;
long long K,k,d;
bool flag;
long long dicstra(long long start);
main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>K;
for(int j=0;j<K;j++){
cin>>k>>d;
edge[p].level=i;
stone[i].push_back(lP(p,P(k,d)));
p++;
}
}
for(int i=1;i<n;i++){
for(int now=0;now<stone[i].size();now++){
for(int j=0;i+1<=n&&j<stone[i+1].size();j++){
edge[stone[i][now].F].to.push_back(P(stone[i+1][j].F,llabs(stone[i][now].S.F-stone[i+1][j].S.F)*(stone[i][now].S.S+stone[i+1][j].S.S)));
}
for(int j=0;i+2<=n&&j<stone[i+2].size();j++){
edge[stone[i][now].F].toskip.push_back(P(stone[i+2][j].F,llabs(stone[i][now].S.F-stone[i+2][j].S.F)*(stone[i][now].S.S+stone[i+2][j].S.S)));
}
}
}
long long ans=LLINF;
for(int i=0;i<stone[1].size();i++){
for(int j=0;j<p;j++){
if(edge[j].level!=1){
for(int l=0;l<100;l++){
edge[j].min[l]=LLINF;
}
}
else{
for(int l=0;l<100;l++){
edge[j].min[l]=0;
}
}
}
flag=false;
ans=min(ans,dicstra(stone[1][i].F));
}
for(int i=0;i<stone[2].size();i++){
for(int j=0;j<p;j++){
if(edge[j].level!=2){
for(int l=0;l<100;l++){
edge[j].min[l]=LLINF;
}
}
else{
for(int l=0;l<100;l++){
edge[j].min[l]=0;
}
}
}
flag=true;
ans=min(ans,dicstra(stone[2][i].F));
}
cout<<ans<<endl;
}
long long dicstra(long long start){
priority_queue<lP,vector<lP>,greater<lP> > que;
if(flag==false){
que.push(lP(0,P(start,m)));
}
else{
que.push(lP(0,P(start,m-1)));
}
while(!que.empty()){
long long nowc=que.top().F;
long long nowp=que.top().S.F;
long long nowm=que.top().S.S;
que.pop();
if(edge[nowp].level+1>n||(nowm>0&&edge[nowp].level+2>n)){
return nowc;
}
for(int i=0;i<edge[nowp].to.size();i++){
long long nextp=edge[nowp].to[i].F;
long long nextc=edge[nowp].to[i].S;
if(edge[nextp].min[nowm]>nowc+nextc){
edge[nextp].min[nowm]=nowc+nextc;
que.push(lP(nowc+nextc,P(nextp,nowm)));
}
}
if(nowm>0){
for(int i=0;i<edge[nowp].toskip.size();i++){
long long nextp=edge[nowp].toskip[i].F;
long long nextc=edge[nowp].toskip[i].S;
if(edge[nextp].min[nowm-1]>nowc+nextc){
edge[nextp].min[nowm-1]=nowc+nextc;
que.push(lP(nowc+nextc,P(nextp,nowm-1)));
}
}
}
}
return LLINF;
}

ステータス

項目 データ
問題 0004 - ぴょんぴょん川渡り
ユーザー名 ei1417
投稿日時 2016-02-09 18:58:22
言語 C++11
状態 Accepted
得点 100
ソースコード長 2848 Byte
最大実行時間 222 ms
最大メモリ使用量 8076 KB

セット

セット 得点 Cases
1 INPUT1 10 / 10 *in01
2 INPUT2 10 / 10 *in02
3 INPUT3 10 / 10 *in03
4 INPUT4 10 / 10 *in04
5 INPUT5 10 / 10 *in05
6 INPUT6 10 / 10 *in06
7 INPUT7 10 / 10 *in07
8 INPUT8 10 / 10 *in08
9 INPUT9 10 / 10 *in09
10 INPUT10 10 / 10 *in10

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
2008-ho-t4-in01 AC 18 ms 2140 KB
1
2008-ho-t4-in02 AC 15 ms 2084 KB
2
2008-ho-t4-in03 AC 12 ms 2272 KB
3
2008-ho-t4-in04 AC 13 ms 2316 KB
4
2008-ho-t4-in05 AC 15 ms 3028 KB
5
2008-ho-t4-in06 AC 87 ms 3340 KB
6
2008-ho-t4-in07 AC 201 ms 4072 KB
7
2008-ho-t4-in08 AC 77 ms 3280 KB
8
2008-ho-t4-in09 AC 78 ms 3304 KB
9
2008-ho-t4-in10 AC 222 ms 8076 KB
10