HDU 6343 Graph Theory Homework（思维）

题目链接：Graph Theory Homework

题意

给定 n n 个节点的完全图，每个节点都有一个权值 wiwi，节点 i i 和节点 jj 之间的边权为 ⌊|wi−wj|−−−−−−−√⌋ ⌊ | w i − w j | ⌋ ，问从节点 1 1 到节点 nn 的最短路径长度。

输入

第一行为一个整数 T (1≤T≤10) T   ( 1 ≤ T ≤ 10 ) ，接下来有 T T 组数据，每组数据第一行为一个整数 n (1≤n≤105)n (1≤n≤105)，第二行有 n n 个整数 w1,w2,⋯,wn (1≤wi≤105)w1,w2,⋯,wn (1≤wi≤105)。

输出

输出节点 1 1 到节点 nn 的最短路径。

样例

输入131 3 5输出2

题解

从节点 1 1 到节点 nn 之间，经历的中间节点越多， 1 1 到 nn 的距离越长，最短距离就是从节点 1 1 到 nn 的边权。

过题代码

#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <climits> #include <cstring> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <map> #include <set> #include <bitset> #include <algorithm> #include <sstream> using namespace std; #define LL long long const int maxn = 100000 + 100; int T, n; int num[maxn]; int main() { #ifdef Dmaxiya freopen("test.txt", "r", stdin); // freopen("out.txt", "w", stdout); #endif // Dmaxiya ios::sync_with_stdio(false); scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%d", &num[i]); } printf("%d\n", (int)sqrt(abs(num[n] - num[1]))); } return 0; }