|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #define INF 1000000 using namespace std; int gr[105][105]; int _mn(int a,int b) { if(a>b) return b; return a; } int _mx(int a,int b) { if(a>b) return a; return b; } int main() { bool f=0; int kase=1; int C,S,Q; int a,b,d; while(cin>>C) { cin>>S>>Q; if(C+S+Q==0) break; for(int i=1;i<105;i++) { for(int j=1;j<105;j++) { if(i==j) gr[i][j]=0; else gr[i][j]=INF; } } for(int i=1;i<=S;i++) { cin>>a>>b>>d; gr[a][b]=d; gr[b][a]=d; } for(int i=1;i<=C;i++) { for(int j=1;j<=C;j++) { for(int k=1;k<=C;k++) { gr[j][k]=_mn(gr[j][k],_mx(gr[j][i],gr[i][k])); } } } if(f) cout<<"\n"; f=1; cout<<"Case #"<<kase++<<"\n"; for(int i=0;i<Q;i++) { cin>>a>>b; if(gr[a][b]==INF) cout<<"no path\n"; else cout<<gr[a][b]<<"\n"; } } return 0; } |