Решение задачи №1368 «Флойд вместо Дейкстры» с ACMP

Условие задачи

Дан ориентированный взвешенный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Найти длину кратчайшего пути из вершины S в вершину T.

Входные данные
В первой строке входного файла INPUT.TXT заданы натуральные числа: N, S и T – число вершин в графе, номера вершин начала и конца пути (N ≤ 50). Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершины в j-ую. Длины могут принимать любые значения от 0 до 106, число -1 означает отсутствие соответствующего ребра. Гарантируется, что на главной диагонали матрицы стоят нули.

Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – минимальную длину пути. Если пути не существует, выведите -1.

Решение на C++


    #include<iostream>

#define INF 1000000000

using namespace std;

int main(){

    int n,i,j,k,s,t;

    cin>>n>>s>>t;s--;t--;

    int a[n][n];

    for(i=0;i<n;++i)

        for(j=0;j<n;++j){

            cin>>a[i][j];

            if(a[i][j]<0)a[i][j]=INF;}

    for(k=0;k<n;++k)

        for(i=0;i<n;++i)

            for(j=0;j<n;++j)

                if(a[i][j]>a[i][k]+a[k][j])

                a[i][j]=a[i][k]+a[k][j];

    if(a[s][t]<INF)cout<<a[s][t];

        else cout<<-1;

     

return 0;}

Условия задач взяты с сайта acmp.ru