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

mb_futar.cpp

Letöltés: mb_futar.cpp

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>

#define INF 100000000

using namespace std;

int n, m, h;

struct csucs_struct
{
    int id;
    int dist;
    bool done;

    list<int> to;
    list<int> weight;
};

csucs_struct* csucsok;

class csucs_compare
{
    public:
    bool operator() (const int& p1, const int& p2) const
    {
        return csucsok[p1].dist>csucsok[p2].dist;
    }
};

void beolvas()
{
    FILE* reader = fopen("futar.be8", "r");
    fscanf(reader, "%d %d %d", &n, &m, &h);
    h--;

    csucsok = new csucs_struct[n];

    for(int i=0; i<n; i++)
    {
        csucsok[i].id=i;
        csucsok[i].dist=INF;
        csucsok[i].done=false;
    }

    int t1, t2, t3;
    for(int i=0; i<m; i++)
    {
        fscanf(reader, "%d %d %d", &t1, &t2, &t3);
        t1--;
        t2--;

        csucsok[t1].to.push_back(t2);
        csucsok[t1].weight.push_back(t3);
    }
}

int main()
{
    beolvas();
    csucsok[h].dist=0;

    priority_queue<int, vector<int>, csucs_compare> pq;
    pq.push(h);

    while(!pq.empty())
    {
        int top=pq.top();
        pq.pop();

        if(csucsok[top].done)
            continue;


        list<int>::iterator it_weight=csucsok[top].weight.begin();
        for(list<int>::iterator it_to=csucsok[top].to.begin(); it_to!=csucsok[top].to.end(); it_to++)
        {
            int alt=csucsok[top].dist+*it_weight;
            if(alt<csucsok[*it_to].dist)
            {
                csucsok[*it_to].dist=alt;
                pq.push(*it_to);
            }
            it_weight++;
        }

        csucsok[top].done=true;
    }

    int mmax=0;

    for(int i=0; i<n; i++)
        printf("%d\n", csucsok[i].dist);

    for(int i=0; i<n; i++)
        mmax=max(mmax, csucsok[i].dist);

    printf("Sol: %d", mmax);
}