|
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 101 102 |
#include <iostream> #include <map> #include <vector> #define INF 1000000000 using namespace std; int L,D; int gr[105][105]; map<int,int> mp; int main() { int kase=1; int t,u,v,c; cin>>t; while(t--) { for(int i=0;i<105;i++) { for(int j=0;j<105;j++) { if(i==j) gr[i][j]=0; else gr[i][j]=INF; } } cin>>L>>D; for(int i=1;i<=D;i++) { cin>>u>>v>>c; if(gr[u][v]>c) { gr[u][v]=c; gr[v][u]=c; } } for(int k=1;k<=L;k++) { for(int i=1;i<=L;i++) { for(int j=1;j<=L;j++) { if(gr[i][j]>gr[i][k]+gr[k][j]) gr[i][j] = gr[i][k]+gr[k][j]; } } } mp.clear(); for(int i=1;i<=L;i++) { if(gr[1][i]!=INF && gr[1][i]==gr[2][i] && gr[1][i]==gr[3][i] && gr[1][i]==gr[4][i] && gr[1][i]==gr[5][i]) { mp[i]=gr[1][i]; } } /*cout<<"sz "<<mp.size()<<"\n"; for(map<int,int>::iterator ii = mp.begin();ii!=mp.end();++ii) cout<<ii->first<<" "<<ii->second<<"\n"; */ if(mp.size()==0) { cout<<"Map "<<kase++<<": "; cout<<"-1\n"; } else { //int MN = INF; int mx =-1; int Mmx =INF; for(map<int,int>::iterator ii = mp.begin();ii!=mp.end();++ii) { int val =ii->first; mx =-1; for(int j=1;j<=L;j++) { if(gr[j][val]>mx) mx = gr[j][val]; } //cout<<"m "<<mx<<"\n"; if(Mmx>mx) Mmx = mx; } cout<<"Map "<<kase++<<": "; if(Mmx==INF) cout<<-1<<"\n"; else cout<<Mmx<<"\n"; } } return 0; } |