Guest User

Untitled

a guest
Feb 23rd, 2018
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.49 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. struct att
  7. {int time; bool able;};
  8.  
  9. struct rebro
  10. {int xn;int xk;int yn;int yk;};
  11.  
  12. int main()
  13. {
  14. int ns, t, nr;
  15. cin>>ns>>t>>nr;
  16.  
  17. att **rasp=new att*[ns];
  18. for (int i=0;i<ns;i++)
  19. rasp[i]=new att[nr];
  20.  
  21. for (int i=0;i<ns;i++)
  22. for (int j=0;j<nr;j++)
  23. {
  24. rasp[i][j].time=-1;
  25. rasp[i][j].able=false;
  26. }
  27.  
  28. for (int i=0;i<nr;i++)
  29. {
  30. int nost;
  31. cin>>nost;
  32. for (int j=0;j<nost;j++)
  33. {
  34. int tost,ttime;
  35. cin>>tost;
  36. cin>>ttime;
  37. rasp[tost-1][i].time=ttime;
  38. }
  39. }
  40.  
  41. for (int i=0;i<nr;i++)
  42. rasp[0][i].able=true;
  43.  
  44. vector <rebro> graph;
  45.  
  46. for (int i=0;i<nr;i++)
  47. for (int j=0;j<ns;j++)
  48. for (int k=0;k<ns;k++)
  49. {
  50. if (j!=k && rasp[j][i].time!=-1 && rasp[k][i].time!=-1)
  51. if (rasp[j][i].time<=rasp[k][i].time)
  52. {
  53. rebro reb;
  54. reb.yn=i;reb.yk=i;
  55. reb.xn=j;reb.xk=k;
  56. graph.push_back(reb);
  57. }
  58. }
  59.  
  60. for (int i=0;i<ns;i++)
  61. for (int j=0;j<nr;j++)
  62. for (int k=0;k<nr;k++)
  63. {
  64. if (j!=k && rasp[i][j].time!=-1 && rasp[i][k].time!=-1)
  65. if (rasp[i][j].time<=rasp[i][k].time)
  66. {
  67. rebro reb;
  68. reb.yn=j; reb.yk=k;
  69. reb.xn=i; reb.xk=i;
  70. graph.push_back(reb);
  71. }
  72. }
  73.  
  74. bool flag=false;
  75. for (int iter=0; iter<ns*nr; iter++)
  76. {
  77. flag=false;
  78. for (int i=0;i<graph.size();i++)
  79. if (rasp[graph[i].xn][graph[i].yn].able && !rasp[graph[i].xk][graph[i].yk].able)
  80. {
  81. rasp[graph[i].xk][graph[i].yk].able=true;
  82. flag=true;
  83. }
  84. if (!flag) break;
  85. }
  86.  
  87. int mintime = 1000000001;
  88. for (int i=0;i<nr;i++)
  89. {
  90. if (rasp[t-1][i].able==true && rasp[t-1][i].time<mintime)
  91. mintime=rasp[t-1][i].time;
  92. }
  93.  
  94. if (mintime==1000000001) cout<<-1;
  95. else cout<<mintime;
  96.  
  97. return 0;
  98. }
Add Comment
Please, Sign In to add comment