编程介的小学生 2017-01-03 15:28 采纳率: 20.5%
浏览 796
已采纳

Card Collection

问题描述 :

In Card Captor Sakura, Sakura is a lovely girl. One day, she opens a magic box containing many cards. Every card has a respective natural force in the real world, such as wind, water, YY, LMY, and so on. Suddenly a gust of wind blows away these cards. Sakura only has a card called “THE_WINDY” in her hand. Sakura knows if any card is not found, disaster comes. So she must collect all the cards. Cards can only be collected one by one. Suppose there are N cards to be collected. It takes Ti to collect the ith card, 1≤i≤N. For the ith card, there is a corresponding card Pi. If card Pi has been collected, it only takes time ti to collect the ith card, where ti<Ti.

Your task is to help Sakura design a schedule that takes the shortest time to collect all cards.

输入:

The input consists of several test cases. Each test case starts with a line giving the number N of cards (1≤N≤100). Each of the next N lines describes a card.

Every card has the format: Name1 Ti Name2 ti, where Name1 and Name2 are cards’ names, consisting of uppercase letters and underlines. The length of cards’ names is no more than 20 characters. Card Name1 is a card to be collected. It takes Ti to collect Card Name1 without Card Name2. And it takes ti to collect Card Name1 with Card Name2, where ti<Ti.

End of input is indicated by a line consisting of a single 0.

输出:

The input consists of several test cases. Each test case starts with a line giving the number N of cards (1≤N≤100). Each of the next N lines describes a card.

Every card has the format: Name1 Ti Name2 ti, where Name1 and Name2 are cards’ names, consisting of uppercase letters and underlines. The length of cards’ names is no more than 20 characters. Card Name1 is a card to be collected. It takes Ti to collect Card Name1 without Card Name2. And it takes ti to collect Card Name1 with Card Name2, where ti<Ti.

End of input is indicated by a line consisting of a single 0.

样例输入:

5
THE_FLY 67 THE_WINDY 39
THE_SHADOW 97 THE_WINDY 49
THE_WATER 139 THE_FLY 69
THE_RAIN 37 THE_WATER 18
THE_WOOD 5 THE_RAIN 1
1
THE_LOOP 35 THE_LOOP 25
0
样例输出:

176
35

  • 写回答

1条回答

  • threenewbee 2017-01-03 15:29
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题