| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1354
WHZ和她的妹子们
Time Limit: 3000ms
Memory Limit: 65536kb Description
WHZ最近在USTC的生活实在太过无聊，于是他通过手机摇微信认识了四只妹子（中科大东、西区，安大，安医附院各一只）。他和四只妹子在网上一见如故，并且顺利的拿到了四只妹子的宿舍地址。现在他要MYT帮他计算一下去找哪只妹子需要花费的时间最少。MYT表示这个问题简直弱爆了，而且她对WHZ去找妹子这种事儿表示很反感很不屑，所以她把这个工作交给了你。为了使得问题变得更加简明，现将问题抽象如下：设给你一个无向图，顶点分别标号1..n，其中有m条路连接着n个顶点。WHZ位于1号顶点，四只妹子分别位于a、b、c、d四个点，由于WHZ找到妹子的心情实在太过迫切，他可以选择一条路来仅使用这条路花费的三分之一（下取整）的时间通过这条路（最多仅能对一条路这么做！）问题是：他能花费最少的时间找到的妹子是哪只？ Input
输入数据包含多组数据，不多于10组。对每组数据： 第1行包括两个数n、m，分别是图中顶点的个数和边的条数 第2行到第m+1行每行有三个数x,y,v，代表从x到y存在一条路，走过这条路花费时间为v。 第m+2行包括四个数a,b,c,d，第i个数代表第i只妹子所在的顶点。 数据范围：n<=100,m<=10000，数据保证无重边 Output
对每组数据输出一行，为了足够有代表性，我们输出这个妹子最喜欢对WHZ说的一句话。（均不包含双引号）妹子1："Hehe" 妹子2："Quxizao" 妹子3："Qushuijiao" 妹子4："Quchidongxi" 如果WHZ到两只妹子所在位置花费的时间相等或者他找不到任何一只妹子，那么他就会很不爽，输出"Shuiwujiaoqu"。 Sample Input
100 0 2 1 3 4 4 4 1 2 10 2 4 10 1 3 1 3 4 100 1 2 3 4 5 4 1 2 10 2 4 10 1 3 1 3 4 100 5 2 3 4 100 0 1 1 1 1 Sample Output
Quxizao Shuiwujiaoqu Qushuijiao Shuiwujiaoqu Source
wyh@USTC ACM team
|