Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <climits>
- #include <graphics.h>
- #include <cmath>
- #include <cstring>
- #define pi 3.14159265359
- using namespace std;
- ifstream f("voiajor.in");
- ofstream g("voiajor.out");
- int l=50,r=200,xc,yc;
- int c[100][100],viz[100],n,start;
- class oras
- {
- int x,y;
- public: constructor(int xd, int yd)
- {
- x=xd;
- y=yd;
- }
- public: void desen()
- {
- line(x-l/2,y-l/2,x-l/2,y+l/2);
- line(x-l/2,y+l/2,x+l/2,y+l/2);
- line(x+l/2,y+l/2,x+l/2,y-l/2);
- line(x+l/2,y-l/2,x-l/2,y-l/2);
- }
- public: void scris(int i)
- {
- char text[10];
- itoa(i,text,10);
- outtextxy(x-l/4,y-l/4,text);
- }
- public: void drum(oras o,int p)
- {
- int dx=o.x-x,dy=o.y-y;
- if (abs(dy/dx)>=1)
- if (dy<0)
- line(x,y-l/2,o.x,o.y+l/2);
- else
- line(x,y+l/2,o.x,o.y-l/2);
- else
- if (dx>0)
- line(x+l/2,y,o.x-l/2,o.y);
- else
- line(x-l/2,y,o.x+l/2,o.y);
- char text[100];
- itoa(p,text,10);
- outtextxy((x+o.x)/2,(y+o.y)/2,text);
- }
- };
- oras v[100];
- void citire()
- {
- f>>n;
- int m;
- f>>m>>start;
- for (int i=1;i<=m;i++)
- {
- int x,y,val;
- f>>x>>y>>val;
- c[x][y]=c[y][x]=val;
- }
- }
- void desenare()
- {
- for (int i=1;i<=n;i++)
- {
- int x,y;
- x=xc+r*sin(2*pi*(float)(i-1)/n);
- y=yc-r*cos(2*pi*(float)(i-1)/n);
- v[i].constructor(x,y);
- v[i].desen();
- v[i].scris(i);
- }
- for (int i=1;i<n;i++)
- for (int j=i+1;j<=n;j++)
- v[i].drum(v[j],c[i][j]);
- }
- void Greedy()
- {
- int cost=0,minim,x,y;
- x=start;
- viz[x]=1;
- g<<x<<' ';
- for (int i=1;i<n;i++)
- {
- minim=INT_MAX;
- for (int j=1;j<=n;j++)
- if (j!=x && !viz[j] && c[x][j]<minim)
- {
- minim=c[x][j];
- y=j;
- }
- cost+=c[x][y];
- g<<y<<' ';
- v[x].drum(v[y],c[x][y]);
- getch();
- viz[y]=1;
- x=y;
- }
- v[x].drum(v[start],c[x][start]);
- cost+=c[x][start];
- g<<start<<'\n'<<cost;
- }
- int main()
- {
- initwindow(1000,700);
- xc=getmaxx()/2,yc=getmaxy()/2;
- citire();
- desenare();
- getch();
- setcolor(RED);
- Greedy();
- getch();
- cleardevice();
- closegraph();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement