Szczegółowe omówienie zadania Piggyback:
Link do powyższego omówienia zadania Piggyback:
https://youtu.be/2RV8_naxzHE?t=1134
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
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;
}