eolymp
bolt
Try our new interface for solving problems
Məsələlər

Dijkstra alqoritmi

Dijkstra alqoritmi

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

İstiqamətlənmiş çəkili qraf verilir. s təpəsindən f təpəsinə qədər ən qısa yolu tapın.

Giriş verilənləri

İlk sətir üç n, sf (1n100, 1s, fn) ədədlərini ehtiva edir, burada n qrafın təpələrinin sayıdır. Qrafın qonşuluq matrisini əks etdirən növbəti n sətrin hər biri n ədəd ehtiva edir, burada i sətri və j sütunu i-dən j-yə olan tili əks etdirir: -1 iki təpə arasında tilin olmadığını bildirir və mənfi olmayan hər hansı ədəd - verilmiş tilin çəkisini bildirir. Matrisin əsas diaqonalı həmişə sıfır qiymətlərini ehtiva edir.

Çıxış verilənləri

Tələb olunan məsafəni və ya verilmiş təpələr arasında yol yoxdursa -1 verməli.

Nümunə

Giriş verilənləri #1
3 1 2
0 -1 2
3 0 -1
-1 4 0
Çıxış verilənləri #1
6