Cod sursa(job #2157226)

Utilizator CozmaCatalinCozma Catalin CozmaCatalin Data 9 martie 2018 13:32:36
Problema Salvare Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <bits/stdc++.h>

std::ifstream in("salvare.in");
std::ofstream out("salvare.out");

using namespace std;

const int MAX = 1002;
int oo = ( 1 << 30);
int D[MAX];
struct Node
{
    int n,distance;

    bool operator < (const Node &a ) const
    {
        return distance > a.distance;
    }
}N[MAX];
bitset < MAX > beenThere;
vector < int > myVector[MAX];

struct CMP
{
    bool operator() ( int x , int y)
    {
        return D[x] > D[y];
    }
};

priority_queue < int , vector < int > ,CMP > myQueue;

int numberOfNodes, Saves;

inline void scanDATA()
{
    in >> numberOfNodes >> Saves;

    for ( int i = 1; i <= numberOfNodes-1 ; ++i)
    {
        int x,y;
        in >> x >> y;
        myVector[x].push_back(y);
        myVector[y].push_back(x);
    }

    for ( int i = 1 ; i <= numberOfNodes ; ++i)
    {
        if( myVector[i].size() == 1)
            {
                myQueue.push(i);
                beenThere[i] = true;
                D[i] = 0;
            }
        else D[i] = oo;
    }
}

int main()
{
    scanDATA();
    while(!myQueue.empty())
    {
        int currentNode = myQueue.top();
        myQueue.pop();
        beenThere[currentNode] = false;
        for ( auto x : myVector[currentNode])
        {
            if(D[currentNode]+1 < D[x])
            {
                D[x] = D[currentNode]+1;
                if(!beenThere[x])
                {
                    beenThere[x] = true;
                    myQueue.push(x);
                }
            }
        }
    }

    for ( int i = 1; i <= numberOfNodes ; ++i)
        {
            N[i].n = i;
            N[i].distance = D[i];
        }

        sort (N+1 , N+numberOfNodes+1);

     out << N[1].distance <<"\n";
        for ( int i = 1 ; i <= Saves ; ++i)
            out << N[i].n <<" ";
}