【北京省选2012 冻结】

【北京省选2012 冻结】

题目背景 BJOI2012 第一轮 DAY2 T1 题目描述 我们考虑最简单的旅行问题吧:现在这个大陆上有 N 个城市,M 条双向的道路。城市编号为 1~N ,我们在 1 号城市,需要到 N号城市,怎样才能最快地到达呢? 这不就是最短路问题吗?我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall 等算法来解决。 现...
【信号连接】

【信号连接】

题目描述 Nico 有一个排练室,她想把新买回来的 IMAX 银幕和放映机与远处的信号连接上,以便排练时可观看 lovelive 直播表演。 已知有 N 个信号发射仪,但其中只有 P 条线路能直接连接(Ai,Bi)(70%数据保证(A,B)只出现一次),且每条线路所花费的钱的就是该线路的长度 Li。保证源信号在 1 号点,排练室在 N 号点,且保证 1 和...
【Geodetic集合】

【Geodetic集合】

题目描述 图 G 是一个无向连通图,没有自环,并且两点之间至多只有一条边。我们定义顶点 v,u 最短路径就是从 v 到 u 经过边最少的路径。所有包含在 v-u 的最短路径上的顶点被称为 v-u 的 Geodetic 顶点,这些顶点的集合记作 I(v, u)。 我们称集合 I(v, u)为一个 Geodetic 集合。 例如下图中,I(2, 5)={2, ...
【NOIP2014提高组 联合权值】

【NOIP2014提高组 联合权值】

题目背景 NOIP2014提高组 Day1 试题。 题目描述 无向连通图 G 有 n 个点,n-1 条边。点从 1 到 n 依次编号,编号为 i 的点的权值为 Wi,每条边的长度均为 1。图上两点 (u, v) 的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对(u, v),若它们的距离为 2,则它们之间会产生 Wu× Wv 的联合权值。 ...