标题

测试数据来自 zxshy/1002

打表提示

输出0,得30分。

题目背景

中士想到了一道绝世好题。

题目描述

中士准备为这道绝世好题加上一个绝世好标题。但是他的语文超级无敌差,想了两年半也没想到这个绝世好标题,只想到了 \(n\) 个词语。根据一些基本的语文语法可得知 \(m\) 个词语关系,形如 \(x(我是空格) y(我是空格)t\) ,意思是 \(y\) 词可以放在 \(x\) 后面,并且这种连接能增加 \(t\) 的分数。一个标题的总分数就是它所有连接的分数之和。他想问你,他能写出的最好的标题分数多高?
又经过了两年半的思考,他发现这个问题对你实在是太难了(实际上是因为出题人T了),所以他帮你确定了第一个词语 \(s\) 。现在,他再次问你,他能写出的最好的标题分数多高?

数据样例

输入

第一行, \(n\) , \(m\) 和 \(s\) 。
接下来 \(n\) 行,是每个词语。
接下来 \(m\) 行,是如题所说的连接。

输出

一个数字,是中士让你算的数字。

样例1

输出

5 4 iam
iam
s
is
a
b
iam a 10
a s 10
s b 10
is a 1

输出

30

样例2

输入

4 4 IOI
IOI
I
ME
AK
IOI AK -1
AK ME 100
IOI ME 50
AK I 1

输出

99

提示

第一个样例最佳为iam-a-s-b,第二个样例最佳为IOI-AK-ME。
关于范围...爆不了int...\(n^3\) 能过...(然而是个稠密图)。
样例无重复词语,无重复边,每个词语只能用一次。

提示*2

\(\small\color{white}朴素最大生成树的都去过第二个样例!!!\)

信息

ID
1225
难度
7
分类
生成树最短路 点击显示
标签
递交数
10
已通过
2
通过率
20%
上传者

相关

在下列训练计划中:

zhongshi的训练