罗米欧与朱丽叶
   

　　罗米欧与朱丽叶正在恋爱，但他们的家庭都不让彼此见面，而朱丽叶非常想见他。庆幸的是，她被允许在星期天下午到一个唱诗班唱歌。她正好是4点离开家，而且要以一条最短路径到达教堂。同样罗米欧每周天在附近一个球场踢球。他也是下午4点离开家，且要抄近路。

　　每个星期天朱丽叶希望在去教堂的路上遇到赶往足球场的罗米欧。朱丽叶不知道到底有没有可能。

　　输入：

　　输入文件包含几个数据块。每块描述一个城市，第一行包含两个数N和M。N是交叉口的数目，M是街道的数目。交叉口以1到N标记。每条街只连接着两个交叉口。第二行有四个数JS、JG、RS、JG，朱丽叶住在JS叉口，教堂在JG叉口，罗米欧家在RS口，足球场在RG口。接下来的M行每行包含三个整数A、B和T，表示一条街，A和B之间是这条街。T是从A到B或从B到A需用的时间。假设从任一个交叉口都可以沿着某些街道到达其他所有交叉口。最后一个数据块后面一行仅包含一个-1。

　　输出：

　　你的任务是计算出对于他们两个人是否都存在一条路使得他们在某个交叉口见面。他们俩只能以最短路径（可能这样的路有几条），朱丽叶与罗米欧同时离开家。若有解输出第一次见面的时间（以分钟为单位），如果无解输出-1

　　Example

　　Input file:　　　　　　　　　　　　 Output file:
　　7 9　　　　　　　　　　　　　　　　　 15
　　1 4 7 6 　　　　　　　　　　　　　　　-1
　　1 2 10
　　2 3 10
　　3 4 10
　　4 5 15
　　5 1 15
　　1 6 10
　　2 7 5
　　5 7 15
　　5 6 10
　　2 1
　　1 2 2 1
　　1 2 10
　　-1
　　 		   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有