jakaria_hossain

UVA - Commandos

Jun 4th, 2019
124
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fast()(ios_base::sync_with_stdio(false),cin.tie(NULL));
  5. int main()
  6. {
  7. int test;
  8. fast()
  9. cin>>test;
  10. for(int t=1; t<=test; t++)
  11. {
  12. int node,edge;
  13. cin>>node>>edge;
  14. int path[node+2][node+2];
  15. for(int i=0; i<=node; i++)
  16. for(int j=0; j<=node; j++)
  17. path[i][j]=101;
  18. for(int i=0; i<edge; i++)
  19. {
  20. int u,v;
  21. cin>>u>>v;
  22. path[u][v]=1;
  23. path[v][u]=1;
  24.  
  25. path[u][u]=0;
  26. path[v][v]=0;
  27. }
  28. for(int i=0; i<node; i++)
  29. {
  30. for(int j=0; j<node; j++)
  31. {
  32. for(int k=0; k<node; k++)
  33. {
  34. if(path[j][k]>path[j][i]+path[i][k])
  35. path[j][k]=path[j][i]+path[i][k];
  36. }
  37. }
  38. }
  39. int s,d,mintime=0;
  40. cin>>s>>d;
  41. for(int i=0;i<node;i++)
  42. {
  43. if(path[s][i]!=101 && path[i][d]!=101)
  44. {
  45. mintime=max(mintime,path[s][i]+path[i][d]);
  46. }
  47. }
  48. cout<<"Case "<<t<<": "<<mintime<<endl;
  49. }
  50. }
RAW Paste Data