#P7587. [2018年杭电多校]Graph Theory Homework
[2018年杭电多校]Graph Theory Homework
题目描述
给定一个有 个顶点的完全无向图。第 个顶点的权值为 。不同顶点 之间的边长为
求从顶点 到顶点 的最短路长度。
输入格式
第一行一个整数 ,表示测试组数。每组先输入一个整数 ,再输入 个整数 。
输出格式
每组输出一行一个整数,表示最短路长度。
样例
1
3
1 3 5
2
数据范围
,,。
给定一个有 n 个顶点的完全无向图。第 i 个顶点的权值为 wi。不同顶点 i,j 之间的边长为
⌊∣wi−wj∣⌋.求从顶点 1 到顶点 n 的最短路长度。
第一行一个整数 T,表示测试组数。每组先输入一个整数 n,再输入 n 个整数 w1,…,wn。
每组输出一行一个整数,表示最短路长度。
1
3
1 3 5
2
1≤T≤10,1≤n≤105,1≤wi≤105。