Advertisement
andreisophie

Comis Voiajor Vizual

Oct 29th, 2019
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.48 KB | None | 0 0
  1. #include <fstream>
  2. #include <climits>
  3. #include <graphics.h>
  4. #include <cmath>
  5. #include <cstring>
  6. #define pi 3.14159265359
  7.  
  8. using namespace std;
  9.  
  10. ifstream f("voiajor.in");
  11. ofstream g("voiajor.out");
  12.  
  13. int l=50,r=200,xc,yc;
  14.  
  15. int c[100][100],viz[100],n,start;
  16.  
  17. class oras
  18. {
  19.     int x,y;
  20.  
  21.     public: constructor(int xd, int yd)
  22.     {
  23.         x=xd;
  24.         y=yd;
  25.     }
  26.  
  27.     public: void desen()
  28.     {
  29.         line(x-l/2,y-l/2,x-l/2,y+l/2);
  30.         line(x-l/2,y+l/2,x+l/2,y+l/2);
  31.         line(x+l/2,y+l/2,x+l/2,y-l/2);
  32.         line(x+l/2,y-l/2,x-l/2,y-l/2);
  33.     }
  34.  
  35.     public: void scris(int i)
  36.     {
  37.         char text[10];
  38.         itoa(i,text,10);
  39.         outtextxy(x-l/4,y-l/4,text);
  40.     }
  41.  
  42.     public: void drum(oras o,int p)
  43.     {
  44.         int dx=o.x-x,dy=o.y-y;
  45.         if (abs(dy/dx)>=1)
  46.             if (dy<0)
  47.                 line(x,y-l/2,o.x,o.y+l/2);
  48.             else
  49.                 line(x,y+l/2,o.x,o.y-l/2);
  50.         else
  51.             if (dx>0)
  52.                 line(x+l/2,y,o.x-l/2,o.y);
  53.             else
  54.                 line(x-l/2,y,o.x+l/2,o.y);
  55.         char text[100];
  56.         itoa(p,text,10);
  57.         outtextxy((x+o.x)/2,(y+o.y)/2,text);
  58.     }
  59. };
  60.  
  61. oras v[100];
  62.  
  63. void citire()
  64. {
  65.     f>>n;
  66.     int m;
  67.     f>>m>>start;
  68.     for (int i=1;i<=m;i++)
  69.     {
  70.         int x,y,val;
  71.         f>>x>>y>>val;
  72.         c[x][y]=c[y][x]=val;
  73.     }
  74. }
  75.  
  76. void desenare()
  77. {
  78.     for (int i=1;i<=n;i++)
  79.     {
  80.         int x,y;
  81.         x=xc+r*sin(2*pi*(float)(i-1)/n);
  82.         y=yc-r*cos(2*pi*(float)(i-1)/n);
  83.         v[i].constructor(x,y);
  84.         v[i].desen();
  85.         v[i].scris(i);
  86.     }
  87.     for (int i=1;i<n;i++)
  88.         for (int j=i+1;j<=n;j++)
  89.             v[i].drum(v[j],c[i][j]);
  90. }
  91.  
  92. void Greedy()
  93. {
  94.     int cost=0,minim,x,y;
  95.     x=start;
  96.     viz[x]=1;
  97.     g<<x<<' ';
  98.     for (int i=1;i<n;i++)
  99.     {
  100.         minim=INT_MAX;
  101.         for (int j=1;j<=n;j++)
  102.             if (j!=x && !viz[j] && c[x][j]<minim)
  103.             {
  104.                 minim=c[x][j];
  105.                 y=j;
  106.             }
  107.         cost+=c[x][y];
  108.         g<<y<<' ';
  109.         v[x].drum(v[y],c[x][y]);
  110.         getch();
  111.         viz[y]=1;
  112.         x=y;
  113.     }
  114.     v[x].drum(v[start],c[x][start]);
  115.     cost+=c[x][start];
  116.     g<<start<<'\n'<<cost;
  117. }
  118.  
  119. int main()
  120. {
  121.     initwindow(1000,700);
  122.     xc=getmaxx()/2,yc=getmaxy()/2;
  123.  
  124.     citire();
  125.     desenare();
  126.     getch();
  127.     setcolor(RED);
  128.     Greedy();
  129.  
  130.     getch();
  131.     cleardevice();
  132.     closegraph();
  133.     return 0;
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement