joc

#include <fstream>
#define INF 0x3f3f3f3f

using namespace std;

ifstream f("joc.in");
ofstream g("joc.out");

int niv[50001],d[50001],T[50001],sol[50001];

struct arc
{
    int x,y,c;
} V[500005];

int main()
{
    int p,n,S,F,m=0;
    f>>p>>n>>S>>F;
    for(int i=1; i<=n; ++i)
    {
        f>>niv[i];
        d[i]=INF;
    }
    for(int nr,i=1; i<=n; i++)
    {
        f>>nr;
        for(int p,j=1; j<=nr; ++j)
        {
            f>>p;
            ++m;
            V[m].x=i;
            V[m].y=p;
            if(niv[i]>niv[p])
                V[m].c=niv[i]/niv[p];
            else V[m].c=niv[p]/niv[i];
        }
    }
    d[S]=0;
    T[S]=0;
    int ok;
    do
    {
        ok=0;
        for(int i=1; i<=m; ++i)
            if(d[V[i].y]>d[V[i].x]+V[i].c)
            {
                d[V[i].y]=d[V[i].x]+V[i].c;
                T[V[i].y]=V[i].x;
                ok=1;
            }
    }
    while(ok);
    if(p==1)
        g<<d[F]<<'\n';
    else
    {
        int r=F,k=0;
        while(r)
        {
            sol[++k]=r;
            r=T[r];
        }
        g<<k<<'\n';
        for(int i=k; i; i--)
            g<<sol[i]<<' ';
    }
    g.close();
    return 0;
}