题解与讨论区 1051: Space Trip

题解与讨论区 1051: Space Trip

[命题人 : ]
时间限制 : 3.000 sec  内存限制 : 64 MB

返回问题页面

题目描述

若干年后,宇宙中发现有 N 个星球(编号从 1 到 N)具有文明,并且其中的一些之间还建立了传送通道,使得各个星球上的居民可以相互往来。但是也有一些星球之间还处于敌对状态。
由于某些原因,你必须从你居住的 1 号星球前往遥远的 N 号星球。这是一次漫长的旅行,为了抵达目的地,你有可能会经过许多别的星球。由于有一些星球目前还处于敌对状态,因此你要避免同时经过这样的星球,比方说,如果星球 A 和 B 目前处于敌对状态,那么假如你访问过 A,之后就决不能再访问 B 了(否则 B 会认为你是间谍而将你囚禁起来),反之若你首先访问过 B,那么也不能再访问 A 了。
现在你手上有一张星际地图,并且你已经知道哪些星球之间目前还处于敌对状态。那么,在不被囚禁的基础上,从起点到终点的最短路程究竟有多长呢?

第1051题的题解