P96580

汽车加油行驶

难度未定分层图最短路

讨论统计 1通过 6提交 16.7%通过率旧版界面

时间限制 1 秒 内存限制 128 MB

题目描述

给定一个N*N的0或1方阵，每行N个值，至N+1行结束。方阵的第i行第j列处的值为1表示在网格交叉点（i，j）处设置了一个油库，为0时表示未设油库。各行相邻两个数以空格分隔。

输入

第一行是N,K,A,B,C的值。

第二行起是一个N*N的0或1方阵，每行N个值，至N+1行结束。方阵的第i行第j列处的值为1表示在网格交叉点（i，j）处设置了一个油库，为0时表示未设油库。各行相邻两个数以空格分隔。

输出

输出仅一行，为最小费用。

样例

样例 1

输入

9 3 2 3 6
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 0

输出

来源

网络流与线性规划24题，一本通

上一题下一题