Алгоритm Yen

Tapın k-cı ən qısa yolu iki sabit zirvə arasında istiqamətsiz qrafda.

Giriş məlumatları

Birinci sətirdə qrafın zirvələrinin sayı n (1 ≤ n ≤ 100), qolların sayı m (1 ≤ m ≤ 4000), və yolun sıra nömrəsi k (1 ≤ k ≤ 500) verilir. Sonrakı sətirlərdə qrafın qolları təsvir edilir - üçlük (u, v, w) zirvələri u və v birləşdirən və ağırlığı w olan qolu göstərir. Sonuncu sətirdə yolun axtarılmalı olduğu iki zirvənin nömrələri s və t verilir.

Qrafda çoxlu qollar və döngələr ola bilməz. Bütün ağırlıqlar müsbətdir və 10000-dən çox deyil. Axtarılan yolun mövcudluğu təmin edilir.

Çıxış məlumatları

Birinci sətirdə yolun tapılmış ağırlığını və zirvələrin sayını iki rəqəm olaraq çıxarın. Növbəti sətirdə yolun özünü - zirvələrin nömrələrinin ardıcıllığını çıxarın.

Nümunələr