hdu1598

find the most comfortable road

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2759 Accepted Submission(s): 1176

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

#include<iostream>
 #include<cstdio> 
#include<algorithm> 
#define INT_MAX 10000000
 using namespace std;
 int father[1000000]; 
int n,m,q; struct edge 
{ 
 int s,e,w; 
}ed[1000005]; 
int find(int x)
 { 
 return x==father[x]?x:father[x]=find(father[x]);
 }
 void union_set(int x,int y)
 { 
 father[find(x)]=find(y); 
} 
void makeset() 
{ 
    int i; 
 for(i=1;i<=n;i++) 
  father[i]=i;
 } 
int cmp(edge a,edge b)
 { 
 return a.w<b.w;
 }
 int main()
 { 
 while(scanf("%d%d",&n,&m)!=EOF) 
 {  
 int i,j,x,y,min;  
 for(i=0;i<m;i++) 
  { 
   scanf("%d%d%d",&ed[i].s,&ed[i].e,&ed[i].w); 
  }  
 scanf("%d",&q);  
 sort(ed,ed+m,cmp); 
  while(q--)  
 {   
 scanf("%d%d",&x,&y); 
   min=INT_MAX; 
   for(i=0;i<m;i++)  
  {  
   makeset();    
 for(j=i;j<m;j++)  
   {   
   union_set(ed[j].s,ed[j].e);  
    if(find(x)==find(y))  
     break;  
   }   
  if(j==m)   
   break;    
 if(min>ed[j].w-ed[i].w)  
    min=ed[j].w-ed[i].w;   
 }   
 if(min==INT_MAX)  
   printf("-1
");  
  else   
  printf("%d
",min); 
  } 
 } 
 return 0;
 }