Collecting Golds
Haralampije je zlatoljub. U okolnih [] gradova nalaze se zlatni ćupovi (1<=C<=1000) koje je postavio lokalni bogataš Miško. Haralampije želi da prikupi što je moguće više ćupova ali tako da se nakoh toga vrati u svoju kuću.
Pomozite Haralampiju da izgradi svoju kuću tako, da može da pokupi najveći moguć broj ćupova.
Napomena: Ćupove u svakom gradu moguće je pokupiti samo jednom.
InputPrva linija standardnog ulaza sadrži ceo broj 1<=N<=1000 gde je N broj gradova. U sledećih N linija nalazi se po jedan ceo Ci, 1<=Ci<=1000, dge je Ci= broj ćupova u gradu i.
Sledeća linija sadrži broj M koji predstavlja broj jednosmernih puteva (1<=M<=N*N). U sledećih M linija nalaze se po dva cela broja A i B, koji predstavljaju put iz grada A u grad B.
Sledeća linija sadrži broj M koji predstavlja broj jednosmernih puteva (1<=M<=N*N). U sledećih M linija nalaze se po dva cela broja A i B, koji predstavljaju put iz grada A u grad B.
OutputNa standardni izlaz u prvi red potrebno je ispisati najveći broj ćupova koje Haralampije može da sakupi.
Ulaz 1:
[c]4
5
4
1
7
6
1 2
2 3
3 1
2 4
4 2
4 4
Izlaz 1:
17Ulaz 2:
5
5
4
1
7
9
5
1 2
2 3
3 1
4 5
5 4
Izlaz 2:
16Ulaz 3:
2
1
100
1
1 2
Izlaz 3:
100Ulaz 1:
Grad Ćupovi:
1 5
2 4
3 1
4 7Haralampije može da sagradi kuću u bilo kom gradu od 1 do 4.
Jedna od dobitnih putanja koja donosi maksimalan broj ćupova je:
*1->2->4->2->3->1
Ćupovi:5+4+1+7=17
Maksimum=17
Input2:
Grad Ćupovi:
1 5
2 4
3 1
4 7
5 9Haralampije može da sagradi kuću u bilo kom gradu od 1 do 5.
Dve interesantne putanje su:
*1->2->3->1 ćupovi:5+4+1=10
*4->5->4 ćupovi:7+9=16
Maksimum=16
Ulaz 3:
Da bi prikupio najveći broj puiteva Haralampiuje treba da izgradi kuću u gradu 2 i da ne putujući nigde pokupi tih 100 Ćupova sa zlatom.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.