Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:不懂题意的童鞋进来看看·····In Reply To:不懂题意的童鞋进来看看····· Posted by:songzhenqi at 2011-07-26 14:30:21 > 首先,题目可能有多组测试数据,每个测试数据的第一行为经纪人数量N(当N=0时, > 输入数据结束),然后接下来N行描述第i(1<=i<=N)个经纪人与其他经纪人的关系 > (教你如何画图)。每行开头数字M为该行对应的经纪人有多少个经纪人朋友(该节点 > 的出度,可以为0),然后紧接着M对整数,每对整数表示成a,b,则表明该经纪人向第a > 个经纪人传递信息需要b单位时间(即第i号结点到第a号结点的孤长为b),整张图为 > 有向图,即弧Vij 可能不等于弧Vji(数据很明显,这里是废话)。当构图完毕后,求 > 当从该图中某点出发,将“消息”传播到整个经纪人网络的最小时间,输出这个经纪 > 人号和最小时间。最小时间的判定方式为——从这个经纪人(结点)出发,整个经纪 > 人网络中最后一个人接到消息的时间。如果有一个或一个以上经纪人无论如何无法收 > 到消息,输出“disjoint”(有关图的连通性,你们懂得,但据其他同学说,POJ测试 > 数据中不会有,就是说,你不判定,一样能过,题目数据够水的)。 > > > 以第一样例为例: > 3 > 2 2 4 3 5 > 2 1 2 3 6 > 2 1 2 2 2 > > 总共3个经纪人,一号经纪人可向2个人传递信息,向2号传递所需时间为4分钟,向3号 > 传递需5分钟。二号经纪人可向2个人传递信息,向1号需2分钟,向3号需6分钟。三号 > 经纪人可向2人传递信息,向1号需2分钟,向2号需2分钟。(以上阿拉伯数字即为对 > 应数据) > > > 将图画出,很容易得出,从3号出发,网络中最后一个得到消息的,需2分钟(可以同时向多人传递,有点不合情理)。所以输出为 3 2。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator