#P7587. [2018年杭电多校]Graph Theory Homework

    ID: 7600 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 4 上传者: 标签>CF1400普及三角不等式向下取整与向上取整二分查找

[2018年杭电多校]Graph Theory Homework

题目描述

给定一个有 nn 个顶点的完全无向图。第 ii 个顶点的权值为 wiw_i。不同顶点 i,ji,j 之间的边长为

⌊∣wi−wj∣⌋.\left\lfloor\sqrt{|w_i-w_j|}\right\rfloor.

求从顶点 11 到顶点 nn 的最短路长度。

输入格式

第一行一个整数 TT,表示测试组数。每组先输入一个整数 nn,再输入 nn 个整数 w1,…,wnw_1,\ldots,w_n。

输出格式

每组输出一行一个整数,表示最短路长度。

样例

1
3
1 3 5
2

数据范围

1≤T≤101\le T\le10,1≤n≤1051\le n\le10^5,1≤wi≤1051\le w_i\le10^5。

原赛题面 PDF