Advertisement
Negru_Diana

Drum (se afiseaza drumul mai mare decat 1)

Nov 11th, 2021
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.23 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. ifstream fin("roy-floyd.in");
  4. ofstream fout("roy-floyd.out");
  5. int n,a[1002][1002],l[1002][1002],ramase[1002],primul[1002];
  6.  
  7. void scrie(int a[][1002])
  8. {
  9. for(int i=1;i<=n;i++)
  10. {
  11. for(int j=1;j<=n;j++)
  12. {
  13. cout<<a[i][j]<<" ";
  14. }
  15. cout<<endl;
  16. }
  17. cout<<endl;
  18. }
  19.  
  20. void drum(int i,int j)
  21. {
  22. int ok=0;
  23. //cout<<i<<" "<<j<<endl;
  24. //cin.get();
  25. for(int k=1;k<=n && !ok;k++)
  26. {
  27. if(a[i][j]==a[i][k]+a[k][j] && k!=i && k!=j)
  28. {
  29. ok=1;
  30. drum(i,k);
  31. drum(k,j);
  32.  
  33. }
  34. }
  35. if(!ok)
  36. {
  37. fout<<j<<" ";
  38. }
  39. }
  40.  
  41. int main()
  42. {
  43. memset(a,10,sizeof(a));
  44. int infinit=a[0][0];
  45.  
  46. int i,j,cost;
  47. fin>>n;
  48. while(fin>>i>>j>>cost)
  49. {
  50. a[i][j]=cost;
  51. l[i][j]=1;
  52. }
  53.  
  54. for(int i=1;i<=n;i++)
  55. {
  56. a[i][i]=0;
  57. }
  58.  
  59.  
  60. for(int k=1;k<=n;k++)
  61. {
  62. for(int i=1;i<=n;i++)
  63. {
  64. for(int j=1;j<=n;j++)
  65. {
  66. if(a[i][j]>a[i][k]+a[k][j] && i!=k && j!=k)
  67. {
  68. a[i][j]=a[i][k]+a[k][j];
  69. l[i][j]=l[i][k]+l[k][j];
  70. }
  71. }
  72. }
  73. scrie(a);
  74.  
  75. }
  76. int afis;
  77. for(int i=1;i<=n;i++)
  78. {
  79. for(int j=1;j<=n;j++)
  80. {
  81. if(a[i][j] && a[i][j]!=infinit)
  82. {
  83. if(l[i][j]>1)
  84. {
  85.  
  86. //fout<<i<<"->"<<j<<": "<<i<<" ";
  87. fout<<i<<" ";
  88. drum(i,j);
  89. fout<<endl;
  90. }
  91.  
  92. //fout<<i<<" ";
  93.  
  94.  
  95.  
  96. //l[i][j]++;
  97. //fout<<endl;
  98.  
  99.  
  100. }
  101. else
  102. {
  103. //cout<<i<<" "<<j<<endl;
  104. }
  105.  
  106. }
  107. }
  108.  
  109. //for(int i=1;i<=n)
  110.  
  111. for(int i=1;i<=n;i++)
  112. {
  113. for(int j=1;j<=n;j++)
  114. {
  115. cout<<l[i][j]<<" ";
  116. }
  117. cout<<endl;
  118. }
  119.  
  120. /*for(int i=1;i<=n;i++)
  121. {
  122. for(int j=1;j<=n;j++)
  123. {
  124. cout<<a[i][j]<<" ";
  125. }
  126. cout<<endl;
  127. }*/
  128.  
  129.  
  130. }
  131.  
  132.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement