Problem Description

XX星有很多城市，城市之间通过一种奇怪的快速公路SARS(Super Air Roam Structure---超级空中漫游结构）进行交流。每条SARS都对行驶在上面的Flycar限制了固定的Speed，同一时候XX星人对 Flycar的“舒适度”有特殊要求。即乘坐过程中最快速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求。flycar必须瞬间提速/降速，痛苦呀 ),

但XX星人对时间却没那么多要求。

要你找出一条城市间的最舒适的路径。(SARS是双向的）。

 

Input

输入包含多个測试实例，每一个实例包含：

第一行有2个正整数n (1<n<=200)和m (m<=1000),表示有N个城市和M条SARS。

接下来的行是三个正整数StartCity,EndCity,speed,表示从表面上看StartCity到EndCity,限速为speedSARS。speed<=1000000

然后是一个正整数Q（Q<11),表示寻路的个数。

接下来Q行每行有2个正整数Start,End, 表示寻路的起终点。

 

Output

每一个寻路要求打印一行，仅输出一个非负整数表示最佳路线的舒适度最快速与最低速的差。假设起点和终点不能到达，那么输出-1。

 

Sample Input

4 4

1 2 2

2 3 4

1 4 1

3 4 2

2

1 3

1 2

 

Sample Output

1

0

中文题目就不用说题意了

并查集，排序加枚举，下边是我理解大神代码猴，自己加的凝视。，唉，，仅仅怪自己太菜

2015，。7，，22


#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

struct node

{

	int sc,ec,speed;

}a[1100];

int f[210];

int n,m;

bool cmp(node a,node b){ return a.speed<b.speed; }

void init() { for(int i=0;i<210;i++) f[i]=i; }

int find(int k) { if(f[k]!=k)	k=find(f[k]);	return k; }

void merge(int a,int b){ a=find(a); b=find(b); if(a!=b) f[a]=b; }

int slove(int s,int e)

{

	int i,j,ans;

	init();

	for(i=0;i<m;i++)//推断是否连通

	{

		merge(a[i].sc,a[i].ec);

	}

	if(find(s)!=find(e)) return -1;//假设不连通就返回-1

	ans=0x3f3f3f;

	for(i=0;i<m;i++)//以每条边为起始边。这条边权就是这条线的最小速度

	{

		init();

		for(j=i;j<m;j++)//依次增加边。直到连通。ans存放最小的差值

		{

			if(a[j].speed-a[i].speed>=ans) continue;

			merge(a[j].sc,a[j].ec);

			if(find(s)==find(e))//假设起点和终点连通时 ，此时的a[j].speed就是这条路线的最大速度

			{

				if(ans>a[j].speed-a[i].speed)

					ans=a[j].speed-a[i].speed;

			}

		}

	}

	return ans;

}

int main(){

	int i,t,s,e;

	while(~scanf("%d%d",&n,&m))

	{

		for(i=0;i<m;i++)

		{

			scanf("%d%d%d",&a[i].sc,&a[i].ec,&a[i].speed);

		}

		sort(a,a+m,cmp);//按权值排序

		scanf("%d",&t);

		while(t--)

		{

			scanf("%d%d",&s,&e);

			printf("%d\n",slove(s,e));

		}

	}

	return 0;

}