问题 23132 --关键路径

23132: 关键路径

时间限制: 1 Sec  内存限制: 128 MB
提交: 36  解决: 6
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][20kb]

题目描述

描述:

    图的连接边上的数据表示其权值,带权值的图称作网。


上图可描述为顶点集为a,b,c,d,e)

边集及其权值为(始点,终点 权值):a b 3

    a c 2 

    b d 5

    c d 7

                                                     c e 4

                                                     d e 6            

  网的源点是入度为0的顶点,汇点是出度为0的顶点。网的关键路径是指从源点到汇点的所有路径中,具有最大路径长度的路径。上图中的关键路径为a->c->d->e,其权值之和为关键路径的长度为15

  本题的要求是根据给出的网的邻接矩阵求该网的关键路径及其长度。


输入

第一行输入一个正整数n1<=n<=5),其代表测试数据数目,即图的数目

第二行输入x(1<=x<=15)代表顶点个数,y(1<=y<=19)代表边的条数

第三行给出图中的顶点集,共x个小写字母表示顶点

接下来每行给出一条边的始点和终点及其权值,用空格相隔,每行代表一条边。

输出

第一个输出是图的关键路径(用给出的字母表示顶点, 用括号将边括起来,顶点逗号相隔)

第二个输出是关键路径的长度

每个矩阵对应上面两个输出,两个输出在同一行用空格间隔,每个矩阵的输出占一行。


样例输入

2
5 6
abcde
a b 3
a c 2
b d 5
c d 7
c e 4
d e 6
4 5
abcd
a b 2
a c 3
a d 4
b d 1
c d 3

样例输出

(a,c) (c,d) (d,e) 15
(a,c) (c,d) 6

提示

作者:梁青青

来源

[提交][状态]