-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy path101_FISHER.cpp
96 lines (87 loc) · 1.5 KB
/
101_FISHER.cpp
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
/*
TASK: Fishmonger
ALGO: dynamic programming
Sample input:
4 7
0 5 2 3
5 0 2 3
3 1 0 2
3 3 2 0
0 2 2 7
2 0 1 2
2 2 0 5
7 2 5 0
0 0
Sample output:
6 6
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=1024;
const int INF=0x3f3f3f3f;
int T,N;
struct state
{
int r , t ;
state()
{
r = t = INF;
}
state(int _r,int _t)
{
r = _r;
t = _t;
}
bool operator<(const state &A)const
{
if( t > T && A.t > T )
return r < A.r;
if( t > T )
return false;
if( A.t > T )
return true;
if( r != A.r )
return r < A.r;
if( t != A.t )
return t < A.t;
return false;
}
};
state dp[MAXN][MAXN];
int risk[MAXN][MAXN];
int dist[MAXN][MAXN];
int main()
{
while(scanf("%d%d",&N,&T)==2 && N+T)
{
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
scanf("%d",&dist[i][j]);
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
scanf("%d",&risk[i][j]);
for(int i = 0;i <= N; i++)
for(int j = 0;j <= T; j++)
dp[j][i]=state();
for(int i = 0; i <= T; i++)
dp[i][N] = state(0,0);
for(int i = 1; i <= T; i++)
{
for(int j = 1; j <= N; j++)
{
for(int k = 1; k <= N; k++)
{
if((j==k)||(i<dist[j][k])) continue;
state next;
next.r = risk[j][k] + dp[i-dist[j][k]][k].r;
next.t = dist[j][k] + dp[i-dist[j][k]][k].t;
if(next < dp[i][j]) dp[i][j]=next;
}
}
}
printf("%d %d\n", dp[T][1].r, dp[T][1].t );
}
return 0;
}