#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define inf 0x7fFFffFF
short nodes, paths, chs;
short ** plst, * viz, * ord, * pord;
unsigned int *** list, * dist, * globd;
char ** name;
inline int cmp( const void * a, const void * b)
{
return strcmp ( name
[ * ( ( const short * ) a
) ] , name
[ * ( ( const short * ) b
) ] ) ; }
inline int comp( const void * a, const void * b)
{
return plst[ * ( ( const short * ) a) ] [ chs] - plst[ * ( ( const short * ) b) ] [ chs] ;
}
short getindex( const char * string)
{
short lo = 1 , hi = nodes, mid, res;
while ( lo <= hi) {
mid = ( lo + hi) / 2 ;
res
= strcmp ( string
, name
[ ord
[ mid
] ] ) ; if ( ! res) {
return ord[ mid] ;
} else if ( res > 0 ) {
lo = mid + 1 ;
} else {
hi = mid - 1 ;
}
}
return 0 ;
}
void read( )
{
short i, j, nbs, nb;
unsigned int cst;
char tmp[ 11 ] ;
name
= ( char ** ) malloc ( ( nodes
+ 1 ) * sizeof ( char * ) ) ; ord
= ( short * ) malloc ( ( nodes
+ 1 ) * sizeof ( short ) ) ; list
= ( unsigned int *** ) malloc ( ( nodes
+ 1 ) * sizeof ( unsigned int ** ) ) ; for ( i = 1 ; i <= nodes; ++ i) {
scanf ( "%s\n %hd" , tmp
, & nbs
) ; ord[ i] = i;
list
[ i
] = ( unsigned int ** ) malloc ( ( nbs
+ 1 ) * sizeof ( unsigned int * ) ) ; list
[ i
] [ 0 ] = ( unsigned int * ) malloc ( sizeof ( unsigned int ) ) ; list[ i] [ 0 ] [ 0 ] = nbs;
for ( j = 1 ; j <= nbs; ++ j) {
scanf ( "%hd %u" , & nb
, & cst
) ; list
[ i
] [ j
] = ( unsigned int * ) malloc ( 2 * sizeof ( unsigned int ) ) ; list[ i] [ j] [ 0 ] = nb;
list[ i] [ j] [ 1 ] = cst;
}
}
qsort ( ord
+ 1 , nodes
, sizeof ( short ) , cmp
) ; plst
= ( short ** ) malloc ( paths
* sizeof ( short * ) ) ; pord
= ( short * ) malloc ( paths
* sizeof ( short ) ) ; globd
= ( unsigned int * ) malloc ( paths
* sizeof ( unsigned int ) ) ; for ( i = 0 ; i < paths; ++ i) {
plst
[ i
] = ( short * ) malloc ( 2 * sizeof ( short ) ) ; pord[ i] = i;
plst[ i] [ 0 ] = getindex( tmp) ;
plst[ i] [ 1 ] = getindex( tmp) ;
}
viz
= ( short * ) malloc ( ( nodes
+ 1 ) * sizeof ( short ) ) ; dist
= ( unsigned int * ) malloc ( ( nodes
+ 1 ) * sizeof ( unsigned int ) ) ; }
short getoptim( )
{
short maxs, maxd, i, * vecs, * vecd;
maxs = maxd = 0 ;
vecs
= ( short * ) calloc ( nodes
+ 1 , sizeof ( short ) ) ; vecd
= ( short * ) calloc ( nodes
+ 1 , sizeof ( short ) ) ; for ( i = 0 ; i < paths; ++ i) {
++ vecs[ plst[ i] [ 0 ] ] ;
++ vecd[ plst[ i] [ 1 ] ] ;
if ( vecs[ plst[ i] [ 0 ] ] > maxs) {
maxs = vecs[ plst[ i] [ 0 ] ] ;
}
if ( vecd[ plst[ i] [ 1 ] ] > maxd) {
maxd = vecd[ plst[ i] [ 1 ] ] ;
}
}
return maxs > maxd ? 0 : 1 ;
}
void process( )
{
short i, j, src, dest, var, flag, old = 0 , ind, first, second;
unsigned int min;
chs = 0 ; //getoptim(); TLE :/
if ( chs) {
first = 1 ;
second = 0 ;
} else {
first = 0 ;
second = 1 ;
}
qsort ( pord
, paths
, sizeof ( short ) , comp
) ; for ( i = 0 ; i < paths; ++ i) {
ind = pord[ i] ;
src = plst[ ind] [ first] ;
dest = plst[ ind] [ second] ;
if ( old == src) {
globd[ ind] = dist[ dest] ;
continue ;
} else {
old = src;
}
for ( j = 0 ; j <= nodes; ++ j) {
viz[ j] = 0 ;
dist[ j] = inf;
}
dist[ src] = 0 ;
var = src;
do {
viz[ var] = 1 ;
for ( j = 1 ; j <= list[ var] [ 0 ] [ 0 ] ; ++ j) {
if ( dist[ var] + list[ var] [ j] [ 1 ] < dist[ list[ var] [ j] [ 0 ] ] ) {
dist[ list[ var] [ j] [ 0 ] ] = dist[ var] + list[ var] [ j] [ 1 ] ;
}
}
flag = 0 ;
min = inf;
for ( j = 1 ; j <= nodes; ++ j) {
if ( dist[ j] < min && ! viz[ j] ) {
min = dist[ j] ;
var = j;
flag = 1 ;
}
}
} while ( flag) ;
globd[ ind] = dist[ dest] ;
}
for ( i = 0 ; i < paths; ++ i) {
}
}
void clean( )
{
short i, j;
nodes = paths = 0 ;
for ( i = 1 ; i <= nodes; ++ i) {
for ( j = 1 ; j <= list[ i] [ 0 ] [ 0 ] ; ++ j) {
}
}
for ( i = 0 ; i < paths; ++ i) {
}
}
int main( )
{
short tests;
//freopen("shpath.in", "rt", stdin);
for ( scanf ( "%hd" , & tests
) ; tests
; -- tests
) { read( ) ;
process( ) ;
clean( ) ;
}
return 0 ;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojZGVmaW5lIGluZiAweDdmRkZmZkZGCgpzaG9ydCBub2RlcywgcGF0aHMsIGNoczsKc2hvcnQqKiBwbHN0LCAqIHZpeiwgKiBvcmQsICogcG9yZDsKdW5zaWduZWQgaW50KioqIGxpc3QsICogZGlzdCwgKiBnbG9iZDsKY2hhcioqIG5hbWU7CgppbmxpbmUgaW50IGNtcChjb25zdCB2b2lkKiBhLCBjb25zdCB2b2lkKiBiKQp7CiAgICByZXR1cm4gc3RyY21wKG5hbWVbKigoY29uc3Qgc2hvcnQqKWEpXSwgbmFtZVsqKChjb25zdCBzaG9ydCopYildKTsKfQoKaW5saW5lIGludCBjb21wKGNvbnN0IHZvaWQqIGEsIGNvbnN0IHZvaWQqIGIpCnsKICAgIHJldHVybiBwbHN0WyooKGNvbnN0IHNob3J0KilhKV1bY2hzXSAtIHBsc3RbKigoY29uc3Qgc2hvcnQqKWIpXVtjaHNdOwp9CgpzaG9ydCBnZXRpbmRleChjb25zdCBjaGFyKiBzdHJpbmcpCnsKICAgIHNob3J0IGxvID0gMSwgaGkgPSBub2RlcywgbWlkLCByZXM7CiAgICB3aGlsZSAobG8gPD0gaGkpIHsKICAgICAgICBtaWQgPSAobG8gKyBoaSkgLyAyOwogICAgICAgIHJlcyA9IHN0cmNtcChzdHJpbmcsIG5hbWVbb3JkW21pZF1dKTsKICAgICAgICBpZiAoIXJlcykgewogICAgICAgICAgICByZXR1cm4gb3JkW21pZF07CiAgICAgICAgfSBlbHNlIGlmIChyZXMgPiAwKSB7CiAgICAgICAgICAgIGxvID0gbWlkICsgMTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBoaSA9IG1pZCAtIDE7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIDA7Cn0KCnZvaWQgcmVhZCgpCnsKICAgIHNob3J0IGksIGosIG5icywgbmI7CiAgICB1bnNpZ25lZCBpbnQgY3N0OwogICAgY2hhciB0bXBbMTFdOwogICAgc2NhbmYoIiVoZCIsICZub2Rlcyk7CiAgICBuYW1lID0gKGNoYXIqKikgbWFsbG9jKChub2RlcyArIDEpICogc2l6ZW9mKGNoYXIqKSk7CiAgICBvcmQgPSAoc2hvcnQqKSBtYWxsb2MoKG5vZGVzICsgMSkgKiBzaXplb2Yoc2hvcnQpKTsKICAgIGxpc3QgPSAodW5zaWduZWQgaW50KioqKSBtYWxsb2MoKG5vZGVzICsgMSkgKiBzaXplb2YodW5zaWduZWQgaW50KiopKTsKICAgIGZvciAoaSA9IDE7IGkgPD0gbm9kZXM7ICsraSkgewogICAgICAgIHNjYW5mKCIlc1xuJWhkIiwgdG1wLCAmbmJzKTsKICAgICAgICBuYW1lW2ldID0gKGNoYXIqKSBtYWxsb2MoKHN0cmxlbih0bXApICsgMSkgKiBzaXplb2YoY2hhcikpOwogICAgICAgIG9yZFtpXSA9IGk7CiAgICAgICAgc3RyY3B5KG5hbWVbaV0sIHRtcCk7CiAgICAgICAgbGlzdFtpXSA9ICh1bnNpZ25lZCBpbnQqKikgbWFsbG9jKChuYnMgKyAxKSAqIHNpemVvZih1bnNpZ25lZCBpbnQqKSk7CiAgICAgICAgbGlzdFtpXVswXSA9ICh1bnNpZ25lZCBpbnQqKSBtYWxsb2Moc2l6ZW9mKHVuc2lnbmVkIGludCkpOwogICAgICAgIGxpc3RbaV1bMF1bMF0gPSBuYnM7CiAgICAgICAgZm9yIChqID0gMTsgaiA8PSBuYnM7ICsraikgewogICAgICAgICAgICBzY2FuZigiJWhkICV1IiwgJm5iLCAmY3N0KTsKICAgICAgICAgICAgbGlzdFtpXVtqXSA9ICh1bnNpZ25lZCBpbnQqKSBtYWxsb2MoMiAqIHNpemVvZih1bnNpZ25lZCBpbnQpKTsKICAgICAgICAgICAgbGlzdFtpXVtqXVswXSA9IG5iOwogICAgICAgICAgICBsaXN0W2ldW2pdWzFdID0gY3N0OwogICAgICAgIH0KICAgIH0KICAgIHFzb3J0KG9yZCArIDEsIG5vZGVzLCBzaXplb2Yoc2hvcnQpLCBjbXApOwogICAgc2NhbmYoIiVoZCIsICZwYXRocyk7CiAgICBwbHN0ID0gKHNob3J0KiopIG1hbGxvYyhwYXRocyAqIHNpemVvZihzaG9ydCopKTsKICAgIHBvcmQgPSAoc2hvcnQqKSBtYWxsb2MocGF0aHMgKiBzaXplb2Yoc2hvcnQpKTsKICAgIGdsb2JkID0gKHVuc2lnbmVkIGludCopIG1hbGxvYyhwYXRocyAqIHNpemVvZih1bnNpZ25lZCBpbnQpKTsKICAgIGZvciAoaSA9IDA7IGkgPCBwYXRoczsgKytpKSB7CiAgICAgICAgcGxzdFtpXSA9IChzaG9ydCopIG1hbGxvYygyICogc2l6ZW9mKHNob3J0KSk7CiAgICAgICAgcG9yZFtpXSA9IGk7CiAgICAgICAgc2NhbmYoIiVzIiwgdG1wKTsKICAgICAgICBwbHN0W2ldWzBdID0gZ2V0aW5kZXgodG1wKTsKICAgICAgICBzY2FuZigiJXMiLCB0bXApOwogICAgICAgIHBsc3RbaV1bMV0gPSBnZXRpbmRleCh0bXApOwogICAgfQogICAgdml6ID0gKHNob3J0KikgbWFsbG9jKChub2RlcyArIDEpICogc2l6ZW9mKHNob3J0KSk7CiAgICBkaXN0ID0gKHVuc2lnbmVkIGludCopIG1hbGxvYygobm9kZXMgKyAxKSAqIHNpemVvZih1bnNpZ25lZCBpbnQpKTsKfQoKc2hvcnQgZ2V0b3B0aW0oKQp7CiAgICBzaG9ydCBtYXhzLCBtYXhkLCBpLCAqIHZlY3MsICogdmVjZDsKICAgIG1heHMgPSBtYXhkID0gMDsKICAgIHZlY3MgPSAoc2hvcnQqKSBjYWxsb2Mobm9kZXMgKyAxLCBzaXplb2Yoc2hvcnQpKTsKICAgIHZlY2QgPSAoc2hvcnQqKSBjYWxsb2Mobm9kZXMgKyAxLCBzaXplb2Yoc2hvcnQpKTsKICAgIGZvciAoaSA9IDA7IGkgPCBwYXRoczsgKytpKSB7CiAgICAgICAgKyt2ZWNzW3Bsc3RbaV1bMF1dOwogICAgICAgICsrdmVjZFtwbHN0W2ldWzFdXTsKICAgICAgICBpZiAodmVjc1twbHN0W2ldWzBdXSA+IG1heHMpIHsKICAgICAgICAgICAgbWF4cyA9IHZlY3NbcGxzdFtpXVswXV07CiAgICAgICAgfQogICAgICAgIGlmICh2ZWNkW3Bsc3RbaV1bMV1dID4gbWF4ZCkgewogICAgICAgICAgICBtYXhkID0gdmVjZFtwbHN0W2ldWzFdXTsKICAgICAgICB9CiAgICB9CiAgICBmcmVlKHZlY3MpOwogICAgZnJlZSh2ZWNkKTsKICAgIHJldHVybiBtYXhzID4gbWF4ZCA/IDAgOiAxOwp9Cgp2b2lkIHByb2Nlc3MoKQp7CiAgICBzaG9ydCBpLCBqLCBzcmMsIGRlc3QsIHZhciwgZmxhZywgb2xkID0gMCwgaW5kLCBmaXJzdCwgc2Vjb25kOwogICAgdW5zaWduZWQgaW50IG1pbjsKICAgIGNocyA9IDA7IC8vZ2V0b3B0aW0oKTsgVExFIDovCiAgICBpZiAoY2hzKSB7CiAgICAgICAgZmlyc3QgPSAxOwogICAgICAgIHNlY29uZCA9IDA7CiAgICB9IGVsc2UgewogICAgICAgIGZpcnN0ID0gMDsKICAgICAgICBzZWNvbmQgPSAxOwogICAgfQogICAgcXNvcnQocG9yZCwgcGF0aHMsIHNpemVvZihzaG9ydCksIGNvbXApOwogICAgZm9yIChpID0gMDsgaSA8IHBhdGhzOyArK2kpIHsKICAgICAgICBpbmQgPSBwb3JkW2ldOwogICAgICAgIHNyYyA9IHBsc3RbaW5kXVtmaXJzdF07CiAgICAgICAgZGVzdCA9IHBsc3RbaW5kXVtzZWNvbmRdOwogICAgICAgIGlmIChvbGQgPT0gc3JjKSB7CiAgICAgICAgICAgIGdsb2JkW2luZF0gPSBkaXN0W2Rlc3RdOwogICAgICAgICAgICBjb250aW51ZTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBvbGQgPSBzcmM7CiAgICAgICAgfQogICAgICAgIGZvciAoaiA9IDA7IGogPD0gbm9kZXM7ICsraikgewogICAgICAgICAgICB2aXpbal0gPSAwOwogICAgICAgICAgICBkaXN0W2pdID0gaW5mOwogICAgICAgIH0KICAgICAgICBkaXN0W3NyY10gPSAwOwogICAgICAgIHZhciA9IHNyYzsKICAgICAgICBkbyB7CiAgICAgICAgICAgIHZpelt2YXJdID0gMTsKICAgICAgICAgICAgZm9yIChqID0gMTsgaiA8PSBsaXN0W3Zhcl1bMF1bMF07ICsraikgewogICAgICAgICAgICAgICAgaWYgKGRpc3RbdmFyXSArIGxpc3RbdmFyXVtqXVsxXSA8IGRpc3RbbGlzdFt2YXJdW2pdWzBdXSkgewogICAgICAgICAgICAgICAgICAgIGRpc3RbbGlzdFt2YXJdW2pdWzBdXSA9IGRpc3RbdmFyXSArIGxpc3RbdmFyXVtqXVsxXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBmbGFnID0gMDsKICAgICAgICAgICAgbWluID0gaW5mOwogICAgICAgICAgICBmb3IgKGogPSAxOyBqIDw9IG5vZGVzOyArK2opIHsKICAgICAgICAgICAgICAgIGlmIChkaXN0W2pdIDwgbWluICYmICF2aXpbal0pIHsKICAgICAgICAgICAgICAgICAgICBtaW4gPSBkaXN0W2pdOwogICAgICAgICAgICAgICAgICAgIHZhciA9IGo7CiAgICAgICAgICAgICAgICAgICAgZmxhZyA9IDE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9IHdoaWxlIChmbGFnKTsKICAgICAgICBnbG9iZFtpbmRdID0gZGlzdFtkZXN0XTsKICAgIH0KICAgIGZvciAoaSA9IDA7IGkgPCBwYXRoczsgKytpKSB7CiAgICAgICAgcHJpbnRmKCIldVxuIiwgZ2xvYmRbaV0pOwogICAgfQp9Cgp2b2lkIGNsZWFuKCkKewogICAgc2hvcnQgaSwgajsKICAgIG5vZGVzID0gcGF0aHMgPSAwOwogICAgZnJlZSh2aXopOwogICAgZnJlZShkaXN0KTsKICAgIGZvciAoaSA9IDE7IGkgPD0gbm9kZXM7ICsraSkgewogICAgICAgIGZyZWUobmFtZVtpXSk7CiAgICAgICAgZm9yIChqID0gMTsgaiA8PSBsaXN0W2ldWzBdWzBdOyArK2opIHsKICAgICAgICAgICAgZnJlZShsaXN0W2ldW2pdKTsKICAgICAgICB9CiAgICAgICAgZnJlZShsaXN0W2ldWzBdKTsKICAgICAgICBmcmVlKGxpc3RbaV0pOwogICAgfQogICAgZnJlZShuYW1lKTsKICAgIGZyZWUobGlzdCk7CiAgICBmb3IgKGkgPSAwOyBpIDwgcGF0aHM7ICsraSkgewogICAgICAgIGZyZWUocGxzdFtpXSk7CiAgICB9CiAgICBmcmVlKHBsc3QpOwogICAgZnJlZShvcmQpOwogICAgZnJlZShwb3JkKTsKICAgIGZyZWUoZ2xvYmQpOwp9CgppbnQgbWFpbigpCnsKICAgIHNob3J0IHRlc3RzOwogICAgLy9mcmVvcGVuKCJzaHBhdGguaW4iLCAicnQiLCBzdGRpbik7CiAgICBmb3IgKHNjYW5mKCIlaGQiLCAmdGVzdHMpOyB0ZXN0czsgLS10ZXN0cykgewogICAgICAgIHJlYWQoKTsKICAgICAgICBwcm9jZXNzKCk7CiAgICAgICAgY2xlYW4oKTsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==