Advertisement
Five_NT

[C++]Probl comis voiajer

Nov 4th, 2013
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None | 0 0
  1. /*
  2.     Un comis voiajor pleaca dintr-un oras, trebuie sa viziteze un nr de orase si se intoarce in orasul de unde a plecat cu efort minim.
  3. Orice oras "i" este legat printr-o sosea de orice oras "j" de lungime "a[i][j]" km. Se cere traseul pe care trebuie sa.l urmeze comis-voiajorul
  4. astfel incat sa parcurga astfel incat sa parcurga un numar minim de km.
  5.  
  6. */
  7. #include<iostream>
  8. #include<fstream>
  9.  
  10. using namespace std;
  11.  
  12. ifstream f("orase.in");
  13.  
  14. int a[50][50],n,i,j,o,s[50],p,pp,mini,distanta;
  15.  
  16. void citire()
  17. {
  18.     f>>n;
  19.     for(i=1; i<=n; i++)
  20.         for(j=1; j<=n; j++)
  21.             f>>a[i][j];
  22. }
  23. int main()
  24. {
  25.     citire();
  26.     do
  27.     {
  28.         cout<<"Orasul de plecare ";
  29.         cin>>o;
  30.     }
  31.     while(o<0 || o>n);
  32.     s[o]=1;
  33.     p=o;
  34.     cout<<"p="<<p<<" ";
  35.     for(i=1; i<n; i++)
  36.     {
  37.         mini=30000;
  38.         for(j=1; j<=n; j++)
  39.             if(s[j]==0 && a[j][p] && mini>a[j][p])
  40.             {
  41.                 mini=a[j][p];
  42.                 pp=j;
  43.             }
  44.         s[pp]=1;
  45.         distanta=distanta+a[pp][p];
  46.         p=pp;
  47.         cout<<pp<<" ";
  48.     }
  49.     cout<<'\n';
  50.     cout<<"cost="<<distanta;
  51.     return 0;
  52. }
  53.  
  54. /* orase.in */
  55. 5
  56. 0 1 5 5 3
  57. 1 0 2 4 1
  58. 5 2 0 6 1
  59. 5 4 6 0 9
  60. 3 1 1 9 0
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement