Span

Descriptionのある国にはNの村があり、Mの道があり、「村村通工事」を実現するために今ペンキを必要としている」N-1の道がある(一部の人はいつもその国のすべてのプロジェクトが海外から輸入されたと言っているので、自国のペンキを塗っただけだ).「調和」はこの国の最大の目標と追求であり、最小価格などは気にしないからだ.あなたが選んだ最長辺と最短辺の差が小さいほどいいことを望んでいます.
Inputの第1行は1つの数字TOTを与えて、どれだけのグループのデータを代表して、Tot<=6は各グループのデータに対して、まずN,Mの下のM行を与えて、1行の3つの数a,b,cはa村とbの村の道路の距離をcに代表します.
Outputは最小差分値を出力、解出力がなければ"-1"を出力する.
Sample Input 1 4 5 1 2 3 1 3 5 1 4 6 2 4 6 3 4 7
Sample Output 1
Data Constraint
Hint[サンプル解釈]1-4,2-4,3-4の3辺を選択する.【データ範囲】1:2≦n≦100 and 0≦m≦n(n−1)/22:各エッジの重み値が10000以下である3:自己ループがなく、重エッジがないことを保証する
. . . . . . 解析では,まずエッジを長さで並べ替え,次に最長エッジを列挙し,さらに大きなエッジから小さいエッジに加算し,結合エッジ数n−1を実現するまで,最後に加えたエッジがその最長エッジに対応する最短エッジである.その後、答えを統計すれば、エッジを追加するときに使用し、セットを調べて維持することができます.
. . . . . . プログラム:

#include
#include
#include
#include
using namespace std;

int fa[200];

struct edge
{
	int a,b,c;
} w[10000];

bool cmp(edge x,edge y)
{
	return x.c>y.c;
}

int find(int x)
{
	if (fa[x]==x) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}

int main()
{
	int tot;
	scanf("%d",&tot);
	while (tot--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for (int i=1;i<=m;i++)
			scanf("%d%d%d",&w[i].a,&w[i].b,&w[i].c);
		sort(w+1,w+m+1,cmp);
		int ans=2147483647;
		for (int i=1;i<=m;i++)
		{
			for (int j=1;j<=n;j++)
				fa[j]=j;
			int tj=0;
			for (int j=i;j<=m;j++)
			{
				int fx=find(w[j].a),fy=find(w[j].b);
				if (fx!=fy)
				{
					fa[fx]=fy;
					tj++;
					if (tj==n-1)
					{
						ans=min(ans,w[i].c-w[j].c);
						break;
					}
				}
			}
		}
		if (ans==2147483647) printf("%d
",-1); else printf("%d
",ans);
	}
	return 0;
}