问题4074--新三国争霸4074: 新三国争霸
时间限制: 1 Sec 内存限制: 512 MB
提交: 0 解决: 0
[提交] [状态] [讨论版] [命题人:]题目描述
jack特别喜欢玩即时战略类游戏，但他觉得那些游戏都有美中不足的地方。灾害总不降临道路，而只降临城市，而且道路不能被占领，没有保护粮草的真实性。于是他就研发了《新三国争霸》。
在这款游戏中，加入灾害对道路的影响（也就是一旦受到了灾害的影响，那么在一定时间内，这条路将不能通过，这段时间里，不安排士兵去占领）和道路的占领权（对于一条道路A-B，至少需要C个士兵才能守住）。
jack可真是高手，占有了N座城市，需要T天防守，只需要派士兵占领一些道路，以确保任何两个城市之间都有路。士兵可不是白干活的，每个士兵每天都要吃掉V的军粮。因为有灾害，所以方案可能有变化。
因为游戏是jack编的，所以他知道什么时候有灾害。jack可是一个很节约的人，他希望这T天在道路的防守上花最少的军粮。
输入
第一行有4个整数N，M，T，V。
(N表示城市数，M表示道路数，T表示需要占领的天数，V表示每个士兵每天吃掉的军粮数)。
以下M行，每行3个数A，B，C。表示A与B有一条路（路是双向的）需要C个士兵才能守住。
第M+2行是一个数P，表示有P个灾害。
以下P行，每行4个数，X，Y，T1，T2。表示X到Y的这条路，保证X到Y的这条路在上面M行中出现过，在T1到T2这几天都会受灾害。
输出
T天在道路的占领上花费最少的军粮，如果到了某一天有两个城市之间不全有路，那整个指挥系统就乱了，输出-1。
样例输入
【样例输入1】
3 3 5 10
1 2 1
2 3 2
1 3 4
1
1 3 2 5
【样例输入2】
3 3 5 10
1 2 10
2 3 2
1 3 1
1
1 3 2 5
【样例输入3】
3 3 5 10
1 2 10
2 3 2
1 3 1
2
1 3 2 2
1 2 3 5
【样例输入4】
3 3 5 10
1 2 10
2 3 2
1 3 1
2
1 3 1 5
1 2 1 5
样例输出
【样例输出1】
150
【样例说明1】
5天的占领是这样安排的：
5天全部是占领1-2 2-3，每天所需要的士兵数是3，一共需要15，花费150。
【样例输出2】
510
【样例说明2】
第1天占领1-3 2-3，需要士兵数是3，第2-5天，因为1-3不通，换成1-2 2-3，每天需要士兵数12，4天需要48，一共需要51个士兵，费用510。
【样例输出3】
240
【样例说明3】
第1天占领1-3 2-3，需要士兵数是3，第2天，因为1-3不通，换成1-2 2-3，需要士兵数12，第3-5天，又改成1-3 2-3，需要3*3=9，一共需要24，费用240。
【样例输出4】
-1
【样例说明4】
因为有2条道路不通，无法使所有路相通，故输出-1。
来源/分类
[提交] [状态]