Omówienie zadania Maraton – Algorytm Dijkstry

Szczegółowe omówienie zadania Maraton (algorytm Dijkstry znajdowania najkrótszej drogi w grafie):

Link do powyższego omówienia zadania Maraton:
https://youtu.be/eCSjwO9wu0I?t=1199


Link do treści zadania Maraton:
https://szkopul.edu.pl/problemset/problem/maraton/site


Zadanie Maraton pomaga w opanowaniu algorytmu Dijkstry – znajdowania najkrótszej drogi  w grafie.
Szczegółowo omawia wykorzystanie tablicy oraz kolejki priorytetowej w algorytmie Dijkstry.

Odnośniki  do poszczególnych punktów (algorytm, kod, złożoność) znajdują się na stronie:
https://oki.org.pl/oki29/

Jak się uczyć na podstawie takiego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019

——-
Kod C++ programu Maraton, który jest omówiony w powyższym filmie i który otrzymuje 100%


#include <bits/stdc++.h>
using namespace std;

const int MAX_WIERZCHOLKOW = 2e5 + 7;
const long long NIESKONCZONOSC = 9e18+11;

vector< pair <int,int> > graf[MAX_WIERZCHOLKOW];
long long tablica_odleglosci[MAX_WIERZCHOLKOW];
priority_queue < pair<long long int, int> > v_do_odwiedzenia;
bool czy_analizowany[MAX_WIERZCHOLKOW]; 

void Dijsktra (int v_odkad_liczymy) {
 int v_analizowany, v_sasiad_analizowanego, dystans_analizowany_sasiad;
 int krawedz;

 tablica_odleglosci[v_odkad_liczymy] = 0;
 v_do_odwiedzenia.push( make_pair(0, v_odkad_liczymy) );
 
 while ( v_do_odwiedzenia.size() > 0 ) {
    v_analizowany = v_do_odwiedzenia.top().second;
    v_do_odwiedzenia.pop();
    if ( czy_analizowany[v_analizowany] == 1 )
       continue;
    czy_analizowany[v_analizowany] == 1;
    for (krawedz=0; krawedz<graf[v_analizowany].size(); ++krawedz) {
       v_sasiad_analizowanego = graf[v_analizowany][krawedz].second;
       dystans_analizowany_sasiad = graf[v_analizowany][krawedz].first;
       if (  tablica_odleglosci[v_analizowany] + dystans_analizowany_sasiad  <  tablica_odleglosci[v_sasiad_analizowanego] ) {
           tablica_odleglosci[v_sasiad_analizowanego] = tablica_odleglosci[v_analizowany] + dystans_analizowany_sasiad;
           v_do_odwiedzenia.push( make_pair(-tablica_odleglosci[v_sasiad_analizowanego], v_sasiad_analizowanego) );
       }
    }
 }
}

int main() {
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 
 int liczba_wierzcholkow, liczba_krawedzi;
 int v_odkad, v_dokad, waga;
 int v_odkad_liczymy;
 long long najwieksza_odleglosc_od_zrodla, v_max;
 int i;

 cin >> liczba_wierzcholkow;  cin >> liczba_krawedzi;

 for (i=1; i<=liczba_wierzcholkow; ++i) {
    tablica_odleglosci[i] = NIESKONCZONOSC;
 }
 for (i=1; i<=liczba_krawedzi; ++i) {
 	cin >> v_dokad; cin >> v_odkad; cin >> waga;
 	graf[v_odkad].push_back( make_pair(waga, v_dokad) );
 }

 cin >> v_odkad_liczymy;

 Dijsktra (v_odkad_liczymy);

 najwieksza_odleglosc_od_zrodla = 0;
 v_max = 0;
 for (i=1; i<=liczba_wierzcholkow; ++i) {
    if ( tablica_odleglosci[i] >= NIESKONCZONOSC )
       continue;
    if ( tablica_odleglosci[i] > najwieksza_odleglosc_od_zrodla ) {
       najwieksza_odleglosc_od_zrodla = tablica_odleglosci[i];
	   v_max = i;
    }
 }
 cout << v_max << " " << najwieksza_odleglosc_od_zrodla << "\n";

 return 0;
}
Link do pliku ze wzorcowym kodem C++ zadania Maraton 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz