#P18425. Jump Graph
Jump Graph
Jump Graph
给定一个 到 的排列,可以用它构造一个有 个顶点的有向图。若从排列的某个位置跳向另一个位置时,中间跳过的所有元素都小于目标位置的元素,就允许这次跳跃;不比较起点的元素。这种图称为该排列的跳跃图。
形式化地,对于 ,当且仅当对所有满足
的下标 都有 时,图中存在有向边 。起点和终点均不属于中间下标。
对于每个顶点,求从它出发到所有其他顶点的最短距离之和。两个顶点间的距离指有向最短路径的边数。可以证明跳跃图总是强连通,所以任意两个顶点之间都存在有向路径。
输入格式
第一行包含一个整数 ,满足 ,表示排列长度。
第二行包含 个整数 。保证 ,且 时 。
输出格式
输出一行 个整数。第 个数表示跳跃图中从顶点 到所有其他顶点的最短距离之和。
样例
输入:
6
1 6 3 2 5 4
输出:
11 7 7 7 6 8
样例说明
原题给出的表如下:

第 行、第 列是从 到 的有向最短距离,每行之和就是相应的输出。
原 PDF 的说明将此表称为“邻接矩阵”,并描述成仅含 ;但原表实际含有 ,逐对按题面正式边定义建图并进行 BFS 得到的恰好是此距离表,且各行之和与完整原样例一致。因此这里更正表名,保留原表像素;边的定义和题目要求均未改变。