PID59 / 最遥远的心
题目描述

题目背景

大家都知道...这个世界上,zmc小菜最爱的人是-----------------------------------------------外婆.

但是,sqybi大牛把题AC的差不多之后,太无聊了,决定去搞点情报玩玩,不仅带人偷拍zmc小菜的照片...还想搜集zmc小菜的人际关系资料....

题目描述

经过百般花招之后,sqybi牛得到了一张zmc小菜的"人物关系网",但是,sqybi牛今天晚上要陪mm,没有时间,而你作为sqybi牛的助手,这个任务只好交给你来完成.

zmc小菜的"人物关系网"上有n个人及他们的名字,每个人之间都有一定的关系,每2个人间的关系亲密度用一个数字表示,数字越大,表示关系越淡薄,数字越小,关系越亲密(当亲密度>=0时),每个人对自己是最亲密的(可以看作亲密度为0).而且A对B的关系亲密度不一定等于B对A的亲密度,这就像爱情一样,GG对MM好,MM却不一定领情......

在这个关系网中,人可以通过别人来增进感情,比如,如果A对B感情亲密度是3,B对C感情亲密度为2,A对C感情亲密度为7,那么在B的努力下,A对C的感情亲密度将为3+2=5而不是7,当然,假定这样的传递只会朝使关系更亲密的方向进行(即让亲密度更小)。

在生活中...暂时没有感情和永远没有感情是不一样的.....所以在这个网中....如果A不能通过任何人到达B,表明A永远不会对B产生感情,如果A对B暂时没有感情,则A到B的数字标记为-1

如果原来A对B暂时没有感情,A对C的亲密度为3,C到B的亲密度为2,则这次改进的结果为A到B的亲密度以5计算

如果原来A对C永远没有感情,A对B暂时没有感情,B对C亲密度为3,则这次改进的结果为A对C也暂时没有感情

Sqybi牛想知道的是...当所有能改进的关系都改进了以后,在这张关系网中,谁对zmc的关系最淡薄,也就是说,谁是最遥远的那一颗心。

注:永远不会产生感情 比 暂时没有感情 淡薄,如果这2种情况都不发生,则认为亲密度最大的关系最淡薄

如果关系最淡薄的不只一人....就以字典序最前的一人名字为最遥远的.....因为..在zmc小菜的字典里.....那个人一定也在前面~!

输入格式

第一行,m(表示有m行信息)

第2...m+1行,每行一个2个字符串name1,name2(长度小于等于14)和一个整数c,用空格隔开,表示name1对name2的亲密度为c,保证name1和name2不相等

zmc的名字为"ZMC"(保证存在),每个人的名字只由大写字母组成

输出格式

一行,有一个字符串name3和一个整数a,用空格隔开

Name3是对zmc关系最淡薄的人的名字,a为Name3是对zmc的关系,如果name3对zmc永远不会产生感情,输出-2,如果name3对zmc暂时没有感情,输出-1,否则则输出name3对zmc的亲密度

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论