---
# System prepended metadata

title: AISD Lista 1

---

# AISD Lista 1

### Zadanie 4
```
Dick()//O(e + nLog(n))
{
    T[1,..,n] = {inf} // koszt dojscia do i-tego wierzcholka;
    T[Vk.ind] = 0;
    pq = new pq(); //pq kolejka priorytetowa (aka kopiec)
    foreach( v in Vk) //sąsiedzi Vk
    {
        T[v.ind] = edge(v, Vk).val;
        pq.Add(T[v.ind]);
    }
    while(pq is not empty)
    {
        i = pq.popMin();
        foreach(v in G[i])
        {
            if(T[v.ind]>T[i] + edge(G[i], v).val)
            {
                T[v.ind] = T[i] + edge(G[i], v).val;
                pq.Add(v.ind);
            }
        }
    }
    return T;
}
NibyDFS(node, T, BLE)//O(e + n)
{
    if(BLE[node.ind] != -1)
    {
        return BLE[node.ind];
    }
    if(node == Uk)
    {
        BLE[node.ind] = 1;
        return 1;
    }
    suma = 0;
    foreach(v in Legalny(node, T))
    {
        suma += NibyDFS(v, T);
    }
    BLE[node.ind] = suma;
    return suma;
}

bool Legalny(node, T) // mniej fest od reszty
{
    L = new List();
    foreach(v in node)
    {
        if(T[v.ind] < T[node.ind])
        {
            L.ADD(v);
        }
    }
    return L;
}
```

### Zadanie inne
___
