Skip to content

11993: 【原1993】调度员二哥

题目

题目描述

author: Weihao Kong 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1993

题目描述

二哥最近交上了好运,找工作连连碰壁的他托关系在一个神奇的国度谋到了一份好差事。二哥成为了一名光荣的列车调度员,他所管理的是该国最重要的CRH运力枢纽。

每天,这条铁路上有\(N\)趟列车,所有乘客都在列车的始发站上车,每趟列车会在沿途的某些站点停靠,每次停靠都会有且仅有一人下车。由于天气原因,CRH运力枢纽的供电负载有限,二哥需要保证每一时刻铁路线上只有一趟列车运行,其他列车需要进站停靠。

而二哥所面临的最大问题是乘客的情绪,每位乘客的愤怒值为该乘客的行程时间。二哥需要决定每辆列车行驶的先后顺序,从而让所有乘客的愤怒值之和最小。

输入格式

第\(1\)行有\(1\)个整数,表示列车数量\(n\)。

接下来有\(n\)行,每行第\(1\)个整数\(m\),表示列车的停站数。第\(2\)到\(m+1\)个整数表示相邻站间的行驶时间。

输出格式

输出一个整数\(s\),表示乘客们愤怒值的总和的最小值。

样例输入1

2
2 2 4
1 3

样例输出1

16

样例解释1

最优调度顺序为2,3,4.
1号列车行驶,到其第1站1名乘客下车,愤怒值为(2)
2号列车行驶,到其第1站1名乘客下车,愤怒值为(2+3)
1号列车行驶,到其第2站1名乘客下车,愤怒值为(2+3+4)
总愤怒值为 2+(2+3)+(2+3+4) = 16

样例输入2

2
2 6 2
2 5 4

样例输出2

44

样例解释2

最优调度顺序为6,2,5,4.
1号列车走,到其第1站1名乘客下车,愤怒值为(6)
1号列车走,到其第2站1名乘客下车,愤怒值为(6+2)
2号列车走,到其第1站1名乘客下车,愤怒值为(6+2+5)
2号列车走,到其第2站1名乘客下车,愤怒值为(6+2+5+4)
总愤怒值为 6+(6+2)+(6+2+5)+(6+2+5+4) = 44

说明

时间限制:1000ms,内存限制:50000kb。

对于全部数据:列车数量\(1 \leq n \leq 100\)。 每列列车停站数小于\(100\)。相邻站间行驶时间\(1 \leq t \leq 30\)

对于60%数据: 列车数量\(1 \leq n \leq 20\)。 每列列车停站数小于\(20\)。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!