Programozás‎ > ‎Feladatok‎ > ‎Futár‎ > ‎Megoldás‎ > ‎

og_futar.cpp

Letöltés: og_futar.cpp

#include <stdio.h>
#include <iostream>

using namespace std;
void beolvas(char*);

int n,m,h;
/*
struct elek
{
    int w;
    int suly;
};
*/
struct csucs_struct
{
    int* el;
};

csucs_struct* cs;
bool* biztos;
int* apa;
int* d;
int ossz;
int at;

int main()
{
    beolvas("futar.be8");

    apa=new int[n+1];
    biztos=new bool[n+1];
    d=new int[n+1];
    for(int i=1; i<n+1; i++)
    {
        apa[i]=10000;
        d[i]=10000;
        biztos[i]=false;
    }
    ossz=0;
    d[h]=0;
    at=h;
   /*  for(int i=1; i<n+1; i++)
    {
        for(int j=1; j<n+1; j++)
        {
            cout << cs[i].el[j]<<"\n";
        }
    }*/
    while(ossz<n)
    {
        ////////////////////////

        int minh=0;
        int min=10000;
        for(int i=1; i<n+1; i++)
        {
            if(((d[i]<min) && (!biztos[i])))
            {
                min=d[i];
                minh=i;
            }
        }
      //////////////////////

        at=minh;
      //                printf("AT: %d\n", at);

        biztos[at]=true;
        ossz++;

        for(int i=1; i<n+1; i++)
        {
            int alt=d[at]+cs[at].el[i];
         //   printf("%d %d (%d %d)\n", alt, d[i], d[at], cs[at].el[i]);
            if(alt<d[i])
            {
                d[i]=alt;
            }
        }

     //   for(int i=1; i<n+1; i++)
       //     printf("%d: %d\n", i, d[i]);

    }
    int min=0;
    for(int i=1; i<n+1; i++)
    {
 //       cout << d[i] << "\n";
        if(d[i]>min)
        {
            min=d[i];
        }

    }
    cout << min;
}

void beolvas(char* file)
{
    FILE* be = fopen(file, "r");
    fscanf(be, "%d", &n);
    fscanf(be, "%d", &m);
    fscanf(be, "%d", &h);
    cs = new csucs_struct[n+1];
    for (int i=1; i<n+1; i++)
    {
        cs[i].el=new int[n+1];
        for(int j=1; j<n+1; j++)
        {
            cs[i].el[j]=10000;
        }
    }
    for(int i=1; i<m+1; i++)
    {
        int t1,t2,t3;
        fscanf(be, "%d", &t1);
        fscanf(be, "%d", &t2);
        fscanf(be, "%d", &t3);
        if(cs[t1].el[t2]>t3)
        {
            cs[t1].el[t2]=t3;
         //   cout << i << " " << t1 << " " << t2 << " " << t3 << "\n";
        }
    }

}

ċ
og_futar.cpp
(2k)
Péter Erben,
2011. nov. 13. 23:19
Comments