Cod sursa(job #2692778)

Utilizator DariusGhercaDarius Gherca DariusGherca Data 3 ianuarie 2021 18:09:35
Problema Sate Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("graf.in");
ofstream g("graf.out");
const int N=75e2+5;
vector <int> mat[N];
int distanta_start[N],distanta_stop[N],nr_ap_distanta[N];
int n,start,stop;
void calc_distanta(int x,int dist[])
{
    bitset <N> vizitat;
    vizitat[x]=1;
    dist[x]=0;
    queue <int> q;
    q.push(x);
    while(!q.empty())
    {
        int t=q.front();
        for(int i=0;i<mat[t].size();i++)
        {
            int p=mat[t][i];
            if(!vizitat[p])
            {
                dist[p]=dist[t]+1;
                vizitat[p]=1;
                q.push(p);
            }
        }
        q.pop();
    }
}
int main()
{
    int m;
    f>>n>>m>>start>>stop;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y;
        mat[x].push_back(y);
        mat[y].push_back(x);
    }
    int mini=INT_MAX;
    calc_distanta(start,distanta_start);
    calc_distanta(stop,distanta_stop);
    for(int i=1;i<=n;i++)
    {
        mini=min(mini,distanta_start[i]+distanta_stop[i]);
    }
    bitset <N> finalizare;
    for(int i=1;i<=n;i++)
    {
        if(distanta_start[i]+distanta_stop[i]==mini)
        {
            nr_ap_distanta[distanta_start[i]]++;
            finalizare[i]=1;
        }
    }
    vector <int> rez;
    for(int i=1;i<=n;i++)
    {
        if(finalizare[i] && nr_ap_distanta[distanta_start[i]]==1)
        {
            rez.push_back(i);
        }
    }
    g<<rez.size()<<"\n";
    for(int i=0;i<rez.size();i++)
    {
        g<<rez[i]<<" ";
    }
    return 0;
}