Advertisement
slowmindead

nodurile comune prin care trec 2 oameni

Nov 21st, 2019
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.62 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4. ifstream f("da.txt");
  5. int a[100][100],n,m,x,y,z,pinf=150,da[100],nu[200],o;
  6.  
  7. void citire()
  8. {f>>n>>m;
  9. for(int i=1;i<=n;i++)
  10. for(int j=1;j<=n;j++)
  11. if(i==j)
  12. a[i][j]=0;
  13. else
  14. a[i][j]=pinf;
  15. for(int i=1;i<=m;i++)
  16. {f>>x>>y>>z;
  17. a[x][y]=z;
  18.  
  19. }
  20. }
  21.  
  22. void afisare()
  23. {for(int i=1;i<=n;i++)
  24. {for(int j=1;j<=n;j++)
  25. if(a[i][j]==pinf)
  26. cout<<"pinf"<<" ";
  27. else
  28. cout<<a[i][j]<<" ";
  29. cout<<endl;
  30.  
  31. }
  32.  
  33. }
  34.  
  35. void rf()
  36. {for(int k=1;k<=n;k++)
  37. for(int i=1;i<=n;i++)
  38. for(int j=1;j<=n;j++)
  39. if(a[i][j]>a[i][k]+a[k][j])
  40. a[i][j]=a[i][k]+a[k][j];
  41. }
  42.  
  43. void descompunere(int i, int j)
  44. {int g=0;
  45. int k=1;
  46. while(k<=n&& !g)
  47. {if(i!=k&& j!=k)
  48. if(a[i][j]==a[i][k]+a[k][j])
  49. {descompunere(i,k);
  50. descompunere(k,j);
  51. g=1;}
  52. k++;}
  53.  
  54. if(!g)
  55. {cout<<j<<" ";
  56. da[o++]=j;}
  57. }
  58.  
  59. void scriu(int nodin,int nodfin)
  60. {if(a[nodin][nodfin]<pinf)
  61. {cout<<"drumul dintre "<<nodin<<" si "<<nodfin<<" are lungimea "<<a[nodin][nodfin]<<endl;
  62. cout<<"drumul este ";
  63. cout<<nodin<<" ";
  64. descompunere(nodin,nodfin);}
  65. else
  66. cout<<"nu exista drum intre cele 2";
  67.  
  68. }
  69.  
  70. void daa()
  71. {for(int i=1;i<=n;i++)
  72. {da[i]=0;
  73.  
  74. }
  75.  
  76. }
  77.  
  78.  
  79.  
  80.  
  81. int main()
  82. {citire();
  83. afisare();
  84. rf();
  85. int unu,doi,trei,patru,h=0;
  86. cout<<endl;
  87. cin>>unu>>doi;
  88. cin>>trei>>patru;
  89. scriu(unu,doi);
  90. cout<<endl;
  91. for(int i=1;i<=o+1;i++)
  92. {nu[i]=da[i];
  93. h++;}
  94. daa();
  95. scriu(trei,patru);
  96. cout<<endl;
  97. cout<<"Nodurile comune prin care trec sunt ";
  98. for(int i=1;i<=o+1;i++)
  99. {for(int j=1;j<=h;j++)
  100. if(nu[j]==da[i] && nu[j]>0)
  101. cout<<nu[j]<<" ";}
  102. cout<<endl;
  103.  
  104. return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement