|
|
| |
|
会面
|
||||
问题描述 来自各自国家的两个外交官，为了完成一项使命来到某一城市进行商讨。他们要安排一个符合以下条件的会面地点。假设他们在同一时刻离开他们所住的旅馆，而且以同样速度步行前往会面地。为了公平起见，他们走的路程一样，且同时到达。这个城市的地图将事先提供给你，地图中的两个顶点之间有（且仅有）一条街道，且标有距离。两个外交官所住的旅馆恰好在某两个顶点上。你的任务是：找一个顶点可以作为会面地点以及两个外交官到这个地点的两条路径，使得会面能尽早地开始（相对于他们从旅馆出发的时间）。同时任何人不能经过同一个顶点两次，而且两个人经过路径没有公共点。 假设这样的点总是可以找到。 输入（meet.inp） 地图中的顶点被标上号，从1到P (1 <= P <= 200)，如果I和J之间有一条街道，则Di,j 是一个整数，表示街道的长度(1 <= Di,j<= 10). 输入文件的第一行有三个整数（之间用空格隔开），第一个整数L，表示街道数(L <=500)。第二、三个整数表示两个外交官所住旅馆的编号。接下来的L行，每行有三个整数i, j 和Di,j ，表示某一街道及其长度。 输出：meet.out 输出文件包含两行，每一行表示一条路径。路径是一个1到P之间的顶点编号序列，整数之间有一个空格，且第一点必须为旅馆的编号，最后一个点必须是会面点的编号。 样例：  meet.inp: meet.out:
|
||||
| 网站导航
| 关于曙光 | 联系我们
| 请提意见 Copyright © FuJian Sunshine Educational Info. Co.,Ltd. 福建曙光教育资讯有限公司 版权所有 |