#include
<
iostream
>
using
namespace
std;
int
N,M;
int
g[
110
][
510
]
=
{
0
};
long
long
f[
110
][
510
]
=
{
0
};
int
p[
110
][
510
]
=
{
0
};
int
l
=
0
,path[
5100
];
int
main()
{
scanf(
"
%d%d
"
,
&
N,
&
M);
for
(
int
i
=
1
;i
<=
N;
++
i)
for
(
int
j
=
1
;j
<=
M;
++
j)
scanf(
"
%d
"
,
&
g[i][j]);
for
(
int
i
=
1
;i
<=
M;
++
i)
f[
1
][i]
=
g[
1
][i];
for
(
int
i
=
2
;i
<=
N;
++
i){
for
(
int
j
=
1
;j
<=
M;
++
j){
f[i][j]
=
f[i
-
1
][j]
+
g[i][j];
p[i][j]
=-
2
;
}
for
(
int
j
=
2
;j
<=
M;
++
j)
if
(f[i][j]
>
f[i][j
-
1
]
+
g[i][j]){
f[i][j]
=
f[i][j
-
1
]
+
g[i][j];
p[i][j]
=-
1
;
}
for
(
int
j
=
M
-
1
;j
>=
1
;
--
j)
if
(f[i][j]
>
f[i][j
+
1
]
+
g[i][j]){
f[i][j]
=
f[i][j
+
1
]
+
g[i][j];
p[i][j]
=
1
;
}
}
int
x,y
=
1
;
for
(
int
i
=
2
;i
<=
M;
++
i)
if
(f[N][i]
<
f[N][y])
y
=
i;
x
=
N;
while
(x
!=
1
){
l
++
; path[l]
=
y;
if
(p[x][y]
==-
2
)
x
--
;
else
y
+=
p[x][y];
}
l
++
; path[l]
=
y;
for
(
int
i
=
l;i
>=
1
;
--
i)
printf(
"
%d\n
"
,path[i]);
return
0
;
}
posted on 2009-05-31 20:32
xfstart07 阅读(151)
评论(0) 编辑 收藏 引用 所属分类:
代码库