天才黑客

题目描述:

SD0062号选手小Q同学为了偷到SDOI7012的试题，利用高超的黑客技术潜入了SDOI出题组的内联网的中央控制系统，然而这个内联网除了配备有中央控制系统，还为内联网中的每条单向网线设定了特殊的通信口令，这里通信口令是一个字符串，不同网线的口令可能不同。这让小Q同学感觉有些棘手，不过这根本难不倒他，很快他就分析出了整个内联网的结构。
内联网中有n个节点（从1到n标号）和m条单向网线，中央控制系统在第1个节点上，每条网线单向连接内联网中的某两个节点，从1号节点出发经过若干条网线总能到达其他任意一个节点。每个节点都可以运行任意的应用程序，应用程序会携带一条通信口令，当且仅当程序的口令与网线的口令相同时，程序才能通过这条网线到达另一端的节点继续运行，并且通过每条网线都需要花费一定的时间。
每个应用程序可以在任意一个节点修改通信口令，修改通信口令花费的时间可以忽略不计，但是为了减小修改量，需要先调用一个子程序来计算当前程序的口令和网线的口令的最长公共前缀（记其长度为len），由于获取网线的口令的某个字符会比较耗时，调用一次这个子程序需要花费len个单位时间。
除此之外，小Q同学还在中央控制系统中发现了一个字典，每条网线的口令都是字典中的某个字符串。具体来说，这个字典是一棵k个节点（从1到k标号）的有根树，其中根是第1个节点，每条边上有一个字符，字符串S在字典中当且仅当存在某个点u使得从根节点出发往下走到u的这条路径上的字符顺次拼接构成S。
现在小Q同学在1号节点同时开启了n - 1个应用程序，这些应用程序同时运行且互不干扰，每个程序的通信口令都为空，他希望用最短的时间把这些程序分别发送到其他节点上，你需要帮小Q同学分别计算出发送到第i(= 2; 3; ::; n)个节点的程序完成任务的最短时间。

输入格式:

第一行是一个正整数T，表示测试数据的组数，对于每组测试数据，
第一行是三个整数n; m; k，分别表示内联网的节点数、内联网的网线条数、字典树的节点数，
接下来m行，每行包含四个整数ai; bi; ci; di(1 ≤ ai; bi ≤ n; 0 ≤ ci ≤ 20000; 1 ≤ di ≤ k)，表示沿着这条网线可以从第ai个节点花费ci个单位时间到达第bi个节点，网线的口令是由从字典树的根到di这个点的路径上的字符顺次拼接构成的字符串（可能为空），需要注意的是这个内联网可能有自环和重边，接下来k - 1行，每行包含三个整数ui; vi; wi(1 ≤ ui; vi ≤ k; 1 ≤ wi ≤ 20000)，表示字典树上有一条ui ! vi的边，边上有字符wi，保证给出的边构成一棵以1为根的有根树，并且每个点连出去的边上的字符互不相同。

输出格式:

对于每组测试数据，输出n - 1行，第i行表示发送到第i + 1个节点的程序完成任务的最短时间。

样例输入:

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

样例输出:

2
7
3

下载附加文件

提示:

时间限制: 3000ms
空间限制: 512MB

---

来源: 山东省选2017day4t1