Cod sursa(job #3134139)

Utilizator nicholas9onicaMike Krack nicholas9onica Data 28 mai 2023 16:12:34
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.75 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream fin("pang.in");
ofstream fout("pang.out");
vector<vector<int>>nod;
int intrari[100003];
int start[100003];
queue<int> q;
struct val1
{
    int nrrelicve=0;
    bool vizitat=false;
    bool isrelicva=false;
};
val1 val[100003];
struct maxim
{
    int valmax=-1;
    int pozvalmax;

};
maxim maxrelicve[100003];
int nrvizite[100003];
int tati[100003];
struct lol
{
    int poz;
    bool corect=false;
};
lol bfs(int intrari[100003],int start[100003],int k,int nr,int nrvizite[100003],maxim maxrelicve[100003],int tati[100003])
{
    while (!q.empty()) {
        q.pop();
    }
    lol boss;
    for(int i=1; i<=nr; i++)
    {
        q.push(start[i]);
    }
    while(!q.empty())
    {
        int frn=q.front();
        q.pop();
        for(int i=0; i<nod[frn].size(); i++)
        {
            if(val[nod[frn][i]].isrelicva==true)
            {
                val[nod[frn][i]].nrrelicve=val[frn].nrrelicve+1;
            }
            else
            {
                val[nod[frn][i]].nrrelicve=val[frn].nrrelicve;
            }
            if(val[nod[frn][i]].nrrelicve>=maxrelicve[nod[frn][i]].valmax)
            {
                maxrelicve[nod[frn][i]].valmax=val[nod[frn][i]].nrrelicve;
                maxrelicve[nod[frn][i]].pozvalmax=frn;
            }
            if(val[nod[frn][i]].vizitat==false)
            {
                nrvizite[nod[frn][i]]++;
            }
            if(nrvizite[nod[frn][i]]==intrari[nod[frn][i]])
            {
                val[nod[frn][i]].vizitat=true;
                val[nod[frn][i]].nrrelicve=maxrelicve[nod[frn][i]].valmax;
                tati[nod[frn][i]]=maxrelicve[nod[frn][i]].pozvalmax;
                q.push(nod[frn][i]);
                if(val[nod[frn][i]].nrrelicve==k)
                {
                    boss.poz=nod[frn][i];
                    boss.corect=true;
                    return boss;
                }
            }

        }

    }
    return boss;
}
int main()
{
    int t,n,m,k;
    fin>>t;
    for(int i=1; i<=t; i++)
    {
        int m1,m2;
        fin>>n>>m>>k;
        nod.clear();
        nod.resize(n+1);
        for(int j=1; j<100003; j++)
        {
            maxrelicve[i].valmax=-1;
            nrvizite[i]=0;
            intrari[i]=0;
            val[i].vizitat=0;
            val[i].isrelicva=0;
            val[i].nrrelicve=0;
            start[i]=0;
        }
        for(int j=0; j<m; j++)
        {
            fin>>m1>>m2;
            nod[m1].push_back(m2);
            intrari[m2]++;
        }
        int pozrelicva;
        for(int j=1; j<=k; j++)
        {
            fin>>pozrelicva;
            val[pozrelicva].isrelicva=true;
            val[pozrelicva].nrrelicve=1;
        }
        int nr=0;
        for(int j=1; j<=n; j++)
        {
            if(intrari[j]==0)
            {
                nr++;
                start[nr]=j;
            }
        }
        int ok=0;
        lol rasp=bfs(intrari,start,k,nr,nrvizite,maxrelicve,tati);
        if( rasp.corect==true)
        {
            ok=1;
            fout<<"Da"<<"\n";
        }
        else
            fout<<"Nu"<<"\n";
        int raspf[100003];
        int num=1;
        int aux=rasp.poz;
        if(ok==1)
        {
            raspf[num]=aux;
            while(tati[aux]>0)
            {
                num++;
                raspf[num]=tati[aux];
                aux=raspf[num];
            }
            for(int j=num; j>=1; j--)
            {
                if(val[raspf[j]].isrelicva==true)
                    fout<<raspf[j]<<" ";
            }
            fout<<"\n";
        }
    }
}