//UVA 10048 - Audiophobia /* 题意:n个点,m条无向路,每条路有一个噪音指数,从两点间的路径中选一条路,使这条路的最大噪音指数最小 思路:排序+并查集 类似克鲁斯卡尔 */ #include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> using namespace std; #define N 105 int map[N][N]; int c,s,q; int bin[N]; struct node{ int a; int b; int c; }edge[N*N]; int cmp(const void *x,const void *y){ return (*(node *)x).c - (*(node *)y).c; } void init(){ int i; for(i = 0; i < N; ++i) bin[i] = i; } int find(int x){ int i,j,r=x; while(r!=bin[r]){ r = bin[r]; } i=x; while(i!=r){ j=bin[i]; bin[i]=r; i=j; } return r; } void merge(int x,int y){ int fx,fy; fx=find(x); fy=find(y); if(fx<fy) bin[fy]=fx; else bin[fx]=fy; } int main(){ int i,j,ca = 1; int a,b; while(scanf("%d %d %d",&c,&s,&q)!=EOF){ if(c == 0 && s == 0 && q ==0) break; for(i = 1; i <= s; ++i){ scanf("%d %d %d",&edge[i].a,&edge[i].b,&edge[i].c); } qsort(edge+1,s,sizeof(edge[0]),cmp); if(ca != 1) printf("\n"); printf("Case #%d\n",ca++); for(i = 1; i <= q; ++i){ scanf("%d %d",&a,&b); init(); for(j = 1; j <= s; ++j){ merge(edge[j].a,edge[j].b); if(find(a) == find(b)) break; } if(j > s) printf("no path\n"); else printf("%d\n",edge[j].c); } } return 0; }