Автопат
На еден автопат се дадени K едно по друго контролни точки нумерирани со вредностите 1..K (првата точка е 1, па 2,...., а последната е K). Првата контролна точка е почетокот на автопатот.
Познати се точните растојанија меѓу N парови контролни точки.
Дадени се две контролни точки: Т1 и Т2. Ако е можно, најдете го растојанието меѓу контролните точки Т1 и Т2. Ако не е можно да се најде растојанието да се отпечати вредност -1.
Забелешка: Во најмалку 10% од тест случаите познатите растојанија ќе бидат за паровите во кои првата точка од парот секогаш е почетната точка од автопатот.
Влез
Во првиот ред се запишани два броја Т1 и Т2 со кои се означени две контролни точки (1<= Т1, Т2 <= 10 000).
Во вториот ред е запишан бројот K(1<= К<= 10 000) што го претставува бројот на контролни точки и бројот N (1<= N<= 100 000) кој го претставува бројот на познати растојанија од една до друга контролна точка.
Во секој од следните N редови се запишани три вредности одделени со празно место: P[i] K[i] D[i], i=1..N. D[i] е растојанието меѓу контролните точки нумерирани со P[i] и K[i]. (1<= P[i]≠K[i] <= 10 000; 1<=D[i] <= 10 000 000 ) .
Излез
Растојанието меѓу контролните точки Т1 и Т2 ако е можно да се најде. Ако растојанието не е можно да се најде, да се отпечати вредност -1.
Ограничувања
Временско ограничување: 500 milliseconds
Мемориско ограничување: 64 megabytes
Примери
влез 3 5 6 2 1 3 6 1 5 10 | излез 4 |
влез 3 5 6 3 1 5 10 3 2 1 2 1 3 | излез 6 |
влез 3 5 6 3 1 5 10 5 2 8 5 6 6 | излез -1 |
Објаснување за првиот тест пример: Има 6 контролни точки. Растојанието меѓу контролните точки 1 и 3 е 6 метри, а растојанието меѓу 1 и 5 е 10 метри. Растојанието меѓу точките 1 и 5 е збир на растојанието меѓу точките 1 и 3 и растојанието меѓу 3 и 5. Оттука растојанието меѓу точките 3 и 5 е 10-6=4 метри.
Објаснување за вториот тест пример: Има 6 контролни точки. Растојанието меѓу контролните точки 1 и 5 е 10 метри. 10 е збир на растојанијата меѓу точките 1 и 3 и растојанието меѓу 3 и 5. Знаеме дека растојанието од 1 до 2 е 3 метри, а од 2 до 3 е 1 метар. Оттука растојанието од 1 до 3 е 4 (=3+1) метри. Добивме дека растојанието меѓу точките 3 и 5 е разлика на растојанието меѓу точките 1 и 5 (10 метри) и 1 и 3 (4 метри). Оттука растојанието до 10-4=6 метри.
Објаснување за третиот тест пример: Познати се растојанијата меѓу точките 1 и 5, 5 и 2 како и 5 и 6. Се бара растојанието меѓу контролните точки 3 и 5. Но, од познатите растојанија не може да го најдеме бараното растојание. Затоа се печати -1.