e-olymp
Məsələlər

Ford-Bellman

Ford-Bellman

Çoxlu sayda tilləri və dövürləri olan istiqamətlənmiş qraf verilir. Hər bir til ədədlə (mənfi də ola bilər) ifadə olunmuş çəkiyə malikdir. Mənfi çəkili dövrün olmadığına zəmanət verilir.

1-ci təpədən digər bütün təpələrə ən qısa yolları tapın.

Giriş verilənləri

Giriş faylının ilk sətrində təpələrin n (1n100) sayı və tillərin m (0m10000) sayı verilir. Növbəti m cütlük tilləri əks etdirir: tilin başlanğıcı, tilin sonu və onun çəkisi (-100-dən 100-ə qədər tam ədədlər).

Çıxış verilənləri

Qrafın 1-ci təpəsindən digər bütün təpələrə qədər olan ən kiçik yolları ifadə edən n ədəd verin. Əgər uyğun təpəyə gedən yol mövcud deyilsə, yolun uzunluğu yerinə 30000 ədədini verin.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
4 5
1 2 10
2 3 10
1 3 100
3 1 -10
2 3 1
Çıxış verilənləri #1
0 10 11 30000