说好的ALS呢?

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 4 总提交人数: 4

题目描述

每一个手办都是有灵魂的,下面这个高达手办,帅到爆炸有木有O-o(自己脑补)。然而要制作这样一件神器却要费不少功夫。假设现在某厂商引进了制作的整套流水车间,决定量产拯救世界。此车间有n条流水线,每条流水线线有m个装配站,编号都为1-m,每条工作线的第i个装配站都执行相同的功能。拼装一个手办要经过m个装配站才能加工完成,经过第i条工作线的第j个装配站要花费p[i][j]的时间,从第i个工作线移动到第j个工作线要花费t[i][j]的时间,请问制造一个高达最少时间是多少?

输入

多组测试数据

对于每一组测试数据,第一行两个整数输入 N,M(100>=N,M>0),分别代表N条工作线和每条线有M个装配站。

接下来N行每行M个数( N*M 的矩阵,第i行第j个数代表描述中的p[i][j] ),0<权值<=100。

接下来N行每行N个数( N*N的矩阵,第i行第j个数代表描述中的t[i][j] ),0<权值<=100。

输出

对于每组数据,输出一行,需要的最少时间

输入样例

3 3
10 1 10
8 5 10
10 10 2
0 5 2
1 0 5
1 1 0

输出样例

14

Hint

可用图论的知识做,加油~

相关推荐