Letöltés: mb_tura.cpp #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define n 3137
#define N 3200
#define r 6367.5
#define pi 3.14159265
using namespace std;
void doit(int s, int f);
struct varos_struct
{
char nev [50];
float latitude;
float longitude;
int el [n];
int el_darab;
};
int m;
varos_struct* varosok;
bool van_el [n][n];
void beolvas(char* fn)
{
FILE* reader = fopen(fn, "r");
varosok = new varos_struct[n];
for(int i=0; i<n; i++)
{
fscanf(reader, "%s %f %f", &varosok[i].nev, &varosok[i].latitude, &varosok[i].longitude);
varosok[i].latitude*=pi/180;
varosok[i].longitude*=pi/180;
}
fclose(reader);
}
void beolvas_2(char* fn)
{
FILE* reader = fopen(fn, "r");
fscanf(reader, "%d", &m);
char v1 [50];
char v2 [50];
int v1_id;
int v2_id;
for(int i=0; i<m; i++)
{
v1_id=-1;
v2_id=-1;
fscanf(reader, "%s %s", &v1, &v2);
for(int j=0; j<n; j++)
{
if(strcmp(v1, varosok[j].nev)==0)
v1_id=j;
if(strcmp(v2, varosok[j].nev)==0)
v2_id=j;
}
if(v1_id!=v2_id && v1_id!=-1 && v2_id!=-1)
{
doit(v1_id, v2_id);
} else
{
printf("fuuu %d %d\n", v1_id, v2_id);
}
}
fclose(reader);
}
float tavolsag(int f_id, int s_id)
{
varos_struct f=varosok[f_id];
varos_struct s=varosok[s_id];
float szamalo = float nevezo = return r*atan2(szamalo, nevezo);
}
void process_map()
{
for(int i=0; i<n; i++)
varosok[i].el_darab=0;
for(int i=0; i<n; i++)
{
if(i%10==0) printf("I: %d\n", i);
for(int j=i; j<n; j++)
if(i!=j && tavolsag(i, j)<=20)
{
van_el[i][j]=true;
varosok[i].el[varosok[i].el_darab++]=j;
van_el[j][i]=true;
varosok[j].el[varosok[j].el_darab++]=i;
}
}
}
void doit(int s, int f)
{
printf("Doing: %d %d (%s %s)\n", s, f, varosok[s].nev, varosok[f].nev);
bool visited [N];
int lista [N];
int melyseg [N];
int apa [N];
for(int i=0; i<N; i++)
{
lista[i]=-1;
apa[i]=-1;
visited[i]=false;
melyseg[i]=-1;
}
lista[0]=s;
apa[s]=s;
visited[s]=true;
melyseg[s]=0;
int at=0;
int ir=1;
while(lista[at]!=-1)
{
int current = lista[at];
at++;
for(int i=0; i<varosok[current].el_darab; i++)
{
int current2=varosok[current].el[i];
if(!visited[current2])
{
visited[current2]=true;
apa[current2]=current;
melyseg[current2]=melyseg[current]+1;
lista[ir++]=current2;
}
}
}
int a=f;
printf("Melyseg: %d\n", melyseg[a]);
while (a!=s && a!=-1)
{
printf("%s ", varosok[a].nev);
a=apa[a];
}
printf("%s", varosok[s].nev);
return;
}
int main()
{
beolvas("magyarorszag.csv");
process_map();
beolvas_2("tura.be");
} |