###### tags: `xivlo`

# Zajęcia 29.03.2021

## Sugerowana kolejność zadań z listy IX
1. Prywatyzacja autostrad
2. A Ty jak szybko piszesz Dijkstrę? *
3. Królestwo Kernali / Najazd Turystów *
4. Bug (A - runda druga)

\* Uwaga na duże liczby!

## Algorytm Dijkstry

Mamy tablice odwiedzonych (vis), odległości (d) [i poprzedników (prev)]*
Mamy tablicę vectorów par - tablica sąsiedztwa z odległościami

Dijkstra(start):
   Zadeklaruj: kolejka priorytetowa par Q
   
   Dla każdego wierzchołka v w G wykonaj
      d[v] := nieskończoność
      [prev[v] := -1]*
   d[start] := 0
   Dodaj parę {0, start} do Q
   Dopóki Q niepuste wykonaj
      v := zdejmij pierwszy wierzchołek w Q
      Jeżeli v odwiedzone: kontunuuj (continue)
      vis[v] := true
      Dla każdego wierzchołka s (sąsiada v) wykonaj
         Jeżeli d[s] > d[v] + odl(v, s) to
            d[s] := d[v] + odl(v, s)
            [prev[v] := u]*
            Dodaj parę {-d[s], s} do Q

\* Niepotrzebne w implementacji, którą nie obchodzi odtworzenie drogi powrotnej

### Uwagi techniczne
#### Kolejka priorytetowa

#include <queue>

//...
priority_queue< pair<int, int> > Q;
Q.push({-x, y});

Q.top(); //← pierwsza para w kolejce {o, v}
Q.top().second; // ← pierwszy wierzchołek v w kolejce
Q.pop(); // usunięcie pierwszej pary z kolejki

#### Nieskończoność

//int
const int INF = 1e9*2; //2 miliardy
//long long
const long long = 1e18;
//unsigned long long
const long long = 1e19;

// można też za pomocą biblioteki climits
#include <climits>
const int INF = LONG_MAX; //największa możliwa liczba w (long) int
const long long INF = LLONG_MAX; //największa możliwa liczba w long long int
const unsigned long long INF = ULLONG_MAX;

## Tablica
https://miro.com/app/board/o9J_lMkPhoU=/
<iframe width="768" height="432" src="https://miro.com/app/live-embed/o9J_lMkPhoU=/?moveToViewport=-768,497,1536,749" frameBorder="0" scrolling="no" allowFullScreen></iframe>