Dzień Dobry,
mam pewien kłopot z zadaniem z pierwszej Olimpiady informatycznej Bajtocja. Mam napisany kod jednak ciągle nie przechodzi wszystkich testów i czy ktoś mógłby doradzić pomóc w poprawieniu kodu aby przechodził wszystkie testy??
Bajtocja
Limit pamięci: 32 MB
Za górami, za lasami, za rzekami, za morzami leży kraj potężny i bogaty zwany Bajtocją. Panuje tam dobrotliwy król Bajtazar I Wielki, słynny ze swej troski o infrastrukturę kraju. W Bajtocji znajduje się 
miast. Władca rozkazał swym nadwornym architektom przygotować projekty nowych ponaddźwiękowych traktów konnych. Jako odpowiedź otrzymał 
propozycji, każda z nich składa się z trzech liczb 
, 
, 
, gdzie 
i 
są miastami końcowymi traktu (trakt łączy te miasta bezpośrednio i nie przebiega przez inne miasta), a 
oznacza koszt zbudowania tego traktu. Każdym traktem można podróżować zarówno z miasta 
do 
, jak i w stronę przeciwną. Zamierzeniem króla jest budowa sieci traktów w taki sposób, aby można było nimi przejechać między każdymi dwoma miastami, być może odwiedzając po drodze inne miejscowości. Bajtazar jest bardzo oszczędnym królem, więc postanowił zgodzić się tylko na taką sieć, która będzie możliwie najtańsza.
Zadanie
Opracuj program, który:
- wczyta ze standardowego liczbę miast, liczbę proponowanych traktów oraz opisy tych traktów,
- dla każdego traktu określi, czy istnieje taka sieć połączeń między miastami, zgodna z królewskimi rozkazami i w której rozpatrywany trakt, wybudowany za wskazaną kwotę, jest wykorzystywany,
- wypisze na standardowe wyjście zestawienie uzyskanych wyników.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite: liczbę miast 
i liczbę proponowanych traktów 
, rozdzielone pojedynczą spacją i spełniające warunki 
, 
. Każdy z kolejnych 
wierszy zawiera po trzy liczby całkowite 
, 
, 
rozdzielone pojedynczymi spacjami, opisujące proponowany trakt, przy czym 
i 
oznaczają miasta będące końcami traktu, zaś 
jest ceną budowy tego traktu (
, 
).
Wyjście
W każdym z kolejnych 
wierszy należy wypisać słowo "TAK" albo "NIE", w zależności od tego, czy można skonstruować plan budowy zgodny z życzeniem króla, dla którego trakt opisany w odpowiednim wierszu jest w nim zawarty. Możesz bezpiecznie założyć, że dla danych wejściowych zawsze istnieje plan budowy spełniający wymogi Bajtazara.
Przykład
Dla danych wejściowych:
6 10
1 2 2
1 6 1
1 5 3
4 1 5
2 6 2
2 3 5
4 3 4
3 5 4
4 5 4
5 6 3
poprawną odpowiedzią jest:
TAK
TAK
TAK
NIE
TAK
NIE
TAK
TAK
TAK
TAK
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
struct trakty
{
int p;
int k;
int w;
string pr;
int kol;
};
bool porownanie(trakty t1,trakty t2)
{
return t1.w > t2.w;
}
bool porownanie1(trakty t1,trakty t2)
{
return t1.kol < t2.kol;
}
int main()
{
int m,n;
cin>>n>>m;
trakty t[m];
int tw = 0;
int tr = 0;
unsigned short tb[301] = {};
int suma = 0;
string yt[n];
for(int r = 0;r<m;r++)
{
cin>>t[r].p>>t[r].k>>t[r].w;
t[r].pr = "TAK";
t[r].kol = r;
}
sort(t, t +m,porownanie);
for(int p = m-1;p>=0;p--)
{
if(tb[t[m-1].k]==0)
{
tb[t[m-1].k] ++;
tb[t[m-1].p] ++;
suma = suma + 2;
tw = tw + t[m-1].w;
}
for(int i = m-1;i>=0;i--)
{
if(tb[t[i].k] == 0 and tb[t[i].p] ==1)
{
tb[t[i].k] ++;
suma = suma + 1;
tw = tw + t[i].w;
if(suma==n)
{
tr = t[i].w;
}
break;
}
if(tb[t[i].p] == 0 and tb[t[i].k] ==1)
{
tb[t[i].p]++;
suma = suma + 1;
tw = tw + t[i].w;
if(suma==n)
{
tr = t[i].w;
}
break;
}
}
}
for(int s=0;s<m;s++)
{
if(tr <t[s].w)
{
t[s].pr = "NIE";
}
}
sort(t, t +m,porownanie1);
for(int i = 0;i<m;i++ )
{
cout<<t[i].pr<<endl;
}
return 0;
}
