Omówienie zadania Piggyback (USACO Silver) – Grafy, BFS

Omówienie zadania Piggyback (USACO Silver) – Grafy, BFS

Szczegółowe omówienie zadania Piggyback:

Link do powyższego omówienia zadania Piggyback:
https://youtu.be/2RV8_naxzHE?t=1134
Link do treści zadania Piggyback:
Zadanie Piggyback to rewelacyjne zadanie które pokazuje algorytm BFS, jego wykorzystanie.
Algorytm BFS jest szeroko stosowany w informatyce, także w trakcie Olimpiad:
https://youtu.be/2RV8_naxzHE?t=4665 

Zadanie pochodzi z Amerykańskiej Olimpiady Informatycznej USACO – poziom SREBRNY który odpowiada :
* II / III etap Olimpiady Informatycznej Juniorów
* I etap Olimpiady Informatycznej

Zadania z USACO dają nam piękny wpis  do CV:
https://youtu.be/QgLyXYmFQeU?t=3507

Zadanie omawia Jan Ebing, prowadzący zajęcia Olimpijskiego Koła Informatycznego.

W rozwiązaniu zadania można użyć innej – wymaganej w USACO – techniki odczytu danych z pliku i zapisu danych do pliku:
https://youtu.be/XQcYAuPheVM?t=5267

—–
Jak się uczyć na podstawie takiego zadania?
https://tiny.pl/7x1gg

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


#include<bits/stdc++.h>
using namespace std;
const int MAXN=44444;
vector<int>conections[MAXN];
int distanceFromBessie[MAXN];
int distanceFromElssie[MAXN];
int distanceFromBarn[MAXN];
int main()
{
    freopen("piggyback.in","r",stdin);
    freopen("piggyback.out","w",stdout);

    int n,m,b,e,p,v,u;
    scanf("%d%d%d%d%d",&b,&e,&p,&n,&m);
    // 1 - Bessie
    // 2 - Elsie
    // n- Barn
    for(int i=1;i<=m;i++){
        cin>>v>>u;
        conections[v].push_back(u);
        conections[u].push_back(v);
    }
    //BFS z 1
    queue<int>Queue;
    Queue.push(1);
    while(!Queue.empty())
    {
        v=Queue.front();
        Queue.pop();
        for(int i=0;i<conections[v].size();i++)
        { 
            // u - sąsiad v
            u=conections[v][i];
            if((distanceFromBessie[u]==0)&&(u!=1))
            {
                distanceFromBessie[u]=distanceFromBessie[v]+1;
                Queue.push(u);
            }
        }
    }
    //BFS z 2
    Queue.push(2);
    while(!Queue.empty())
    {
        v=Queue.front();
        Queue.pop();
        for(int i=0;i<conections[v].size();i++)
        {
            u=conections[v][i];
            if((distanceFromElssie[u]==0)&&(u!=2)){
                distanceFromElssie[u]=distanceFromElssie[v]+1;
                Queue.push(u);
            }
        }
    }
    //BFS z n
    Queue.push(n);
    while(!Queue.empty())
    {
        v=Queue.front();
        Queue.pop();
        for(int i=0;i<conections[v].size();i++)
        {
            u=conections[v][i];
            if((distanceFromBarn[u]==0)&&(u!=n)){
                distanceFromBarn[u]=distanceFromBarn[v]+1;
                Queue.push(u);
            }
        }
    }

    int minEnergy=1e9+7;
    for(int i=1;i<=n;i++)
    {
        minEnergy=min(minEnergy,distanceFromBessie[i]*b+distanceFromElssie[i]*e+distanceFromBarn[i]*p);
    }
    printf("%d",minEnergy);
    return 0;
}
Link do pliku ze wzorcowym kodem C++ zadania Piggyback 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz