← 返回题目列表

AtCoder · icpc2013summer_day4_i

I. 多路径故事

中文机器翻译题面 查看原题

问题陈述

你是一名热爱美少女游戏(约会模拟游戏的子类型)的程序员。上周五发布的一款名为《漂浮的心》的游戏,刚刚到了你家。这个游戏有多个故事。当你完成所有这些故事时,你可以获得女主角惠的特殊人物。所以,你要赶紧来玩游戏吧!不过,我们先冷静一下,想想如何在最短的时间内完成所有的故事。

事实上,你拥有可以让你了解游戏分支点结构的特殊技能。通过使用该技能,你发现有 n 本场比赛的分支点和 i第一个分支点有 k_{i} 选择。这个游戏太复杂了,有多条路线可以到达 i可能是第一个分支点。您还注意到,这需要 c_{ij} 分钟出发 i-第一个分支点到另一个分支点(或终点),如果您选择 j-第一个选择 i- 第一个分支点。当然,你需要选择所有分支点上的所有选项,并阅读一个分支点和另一个分支点(或结局)之间的故事来完成所有这些故事。此外,您可以假设返回游戏开始(“重置”)并从开始玩到第一个分支点只需要微不足道的时间。

游戏说明书上说,这款游戏有一个名为“快速保存”的附加功能,该功能可以让你记录当前正在玩的点,并在以后随时返回那里。但是,此功能对于某些错误不起作用。因此,如果你到达结局或中途退出游戏,你每次都必须从第一个分支点重新开始。修复此错误的任何补丁尚未发布。这是对速度最快的玩家强加的磨难。

好吧,我们来估算一下在最短的时间内完成所有故事需要多长时间。


输入

数据集以以下格式给出。

n
k_{1} t_{11} c_{12} ... t_{1k_{1}} c_{1k_{1}}
:
:
k_{n} t_{n1} c_{n2} ... t_{nk_{n}} c_{nk_{n}}

数据集的第一行包含一个整数 n (2 \leq n \leq 1{,}000),表示本场比赛的分支点数。以下 n 线描述了分支点。的 i第行描述了ID号的分支点 i。第一个整数 k_{i} (0 \leq k_{i} \leq 50) 是在 i- 第一个分支点。 k_{i} ≥0 意味着 i第一个分支点是一个结局。下一步 2k_{i} 整数 t_{ij} (1 \leq t_{ij} \leq n)和 c_{ij} (0 \leq c_{i}j \leq 300) 是选择的信息。 t_{ij} 表示选择后下一个分支点的 ID 号。 j-第一个选择。 c_{ij} 表示阅读故事之间的时间 i第一个分支点和 t_{ij}- 第一个分支点。 ID为1的分支点是第一个分支点。您可以假设所有分支点和终点都可以从第一个分支点到达。您还可以假设游戏中没有循环,即在不重置的情况下不能多次到达分支点。

输出

打印一行中最短的时间。


样本输入 1

2
1 2 2
0

样本输入 1 的输出

2

示例输入 2

6
2 2 1 3 2
2 4 3 5 4
2 5 5 6 6
0
0
0

样本输入 2 的输出

24

示例输入 3

6
3 2 100 3 10 3 10
1 4 100
1 4 10
3 5 1 5 1 6 1
0
0

样本输入 3 的输出

243