问题 C: 带权路径计数
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:3
解决:2
题目描述
给定一个 的网格,每个格子 上有一个非负整数 ,表示经过该格子需要付出的代价。一个人从左上角 出发,只能向右或向下移动,到达右下角 。
现在定义一条路径的代价为该路径上所有格子(包括起点和终点)的权值之和。请你求出所有路径中代价的最小值,以及在最小代价下的路径条数。
注意:如果存在多条路径达到最小代价,需要输出这些路径的条数。
输入
-
第一行两个整数 ()。
-
接下来 行,每行 个整数,表示每个格子的权值 ()。
输出
输出两个整数,分别表示最小代价和对应的路径条数(用空格分隔)。
样例输入 复制
3 3
1 3 1
1 5 1
4 2 1
样例输出 复制
7 1
提示
1≤n,m≤100
0 ≤ w i , j ≤ 100
0≤w i,j ≤100