|
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include <iostream> #define INF 100000000 using namespace std; int graph[85][85]; int feast[85][85]; int main() { int C,R,Q; int a,b,c; int kase=0; while(cin>>C) { cin>>R>>Q; if(C==0 && R==0 && Q==0) break; for(int i=1;i<=C;i++) { for(int j=1;j<=C;j++) { if(i==j) graph[i][j] = 0; else graph[i][j] = feast[i][j]=INF; } } for(int i=1;i<=C;i++) { int g; cin>>g; feast[i][i]=g; } for(int i=1;i<=R;i++) { cin>>a>>b>>c; graph[a][b]=c; graph[b][a]=c; feast[a][b]= feast[b][a] = max(feast[a][a],feast[b][b]); } for(int k=1;k<=C;k++) { for(int i=1;i<=C;i++) { for(int j=1;j<=C;j++) { if(graph[i][j]+feast[i][j]>graph[i][k]+graph[k][j]+max(feast[i][k],feast[k][j])) { graph[i][j] = graph[i][k]+graph[k][j]; feast[i][j] = max(feast[i][k],feast[k][j]); } } } } for(int k=1;k<=C;k++) { for(int i=1;i<=C;i++) { for(int j=1;j<=C;j++) { if(graph[i][j]+feast[i][j]>graph[i][k]+graph[k][j]+max(feast[i][k],feast[k][j])) { graph[i][j] = graph[i][k]+graph[k][j]; feast[i][j] = max(feast[i][k],feast[k][j]); } } } } if(kase) cout<<"\n"; cout<<"Case #"<<++kase<<"\n"; for(int i=1;i<=Q;i++) { cin>>a>>b; if(graph[a][b]+feast[a][b]>=INF) cout<<-1<<"\n"; else cout<<graph[a][b]+feast[a][b]<<"\n"; //cout<<graph[a][b]; } } return 0; } |