{"draftJsState":{"blocks":[{"data":{"image":{"id":"62c51440f154c93e3a6b6f72"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Условия задачи","type":"atomic:image","key":"29jf8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Условие задачи","type":"header-two","key":"2cj2"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Дан ориентированный взвешенный граф. Вам необходимо найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.","type":"unstyled","key":"62ife"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Алгоритм решения","type":"header-two","key":"aibb8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"В задаче следует реализовать алгоритм Флойда. В ячейках входной (начальной) матрицы поставим большое натуральное число (вместо -1) вместо кратчайшего пути (если остается это число, значит, пути просто не существует). Затем в матрице кратчайших расстояний следует найти наибольшее число (отличное от нашего максимального, присвоенного в самом начале) – оно и будет максимальным кратчайшим расстоянием.","type":"unstyled","key":"a99ak"},{"data":{"image":{"id":"62c5174648e95c54658cba94"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Графическое представление алгоритма Флойда","type":"atomic:image","key":"b823r"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"У нас уже есть имеющиеся пути. Мы вычисляем пути для всех вершин и оставляем кратчайший, то есть:","type":"unstyled","key":"5fvki"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Если кратчайший путь из u в v, содержащий только вершины из множества {1..i}{1..i}, проходит через вершину i, то кратчайшим путем из u в v является кратчайший путь из u в i, объединенный с кратчайшим путем из i в v. В противном случае, когда этот путь не содержит вершины i, кратчайший путь из u в v, содержащий только вершины из множества {1..i}{1..i} является кратчайшим путем из u в v, содержащим только вершины из множества {1..i−1}{1..i−1}.","type":"unstyled","key":"9rlo2"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Решение на с++","type":"header-two","key":"5vlrs"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":54,"offset":0,"style":"BOLD"}],"text":"Полное решение смотри на картинке, прикрепленной ниже!","type":"unstyled","key":"8ej5h"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"using namespace std;","type":"unstyled","key":"7uq5s"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":14,"style":"BOLD"},{"length":26,"offset":15,"style":"ITALIC"}],"text":"int main(){ // основная функция программы","type":"unstyled","key":"1l38m"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"int n,i,j,k;","type":"unstyled","key":"a7ps3"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":34,"offset":11,"style":"ITALIC"}],"text":"cin>>n; // считывание количества вершин графа","type":"unstyled","key":"1eaqn"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":15,"offset":17,"style":"ITALIC"}],"text":"int a[n][n]; // создание матрицы","type":"unstyled","key":"5k2cd"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":50,"offset":20,"style":"ITALIC"}],"text":"for(i=0;i>a[i][j];","type":"unstyled","key":"4dt7e"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":130,"offset":30,"style":"ITALIC"}],"text":"if(a[i][j]<0)a[i][j]=INF;} // INF - изначально присваиваем большое число для дальнейшего вычисления кратчайшего расстояние. Изначально кратчайшее расстояние INF","type":"unstyled","key":"3ir2j"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":27,"offset":20,"style":"ITALIC"}],"text":"for(k=0;ka[i][k]+a[k][j])","type":"unstyled","key":"clfop"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"a[i][j]=a[i][k]+a[k][j];","type":"unstyled","key":"9e4c"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"k=0;","type":"unstyled","key":"dml1k"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":55,"offset":17,"style":"ITALIC"}],"text":"for(i=0;ik)","type":"unstyled","key":"fk1am"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"k=a[i][j];","type":"unstyled","key":"17ueg"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":12,"offset":12,"style":"ITALIC"}],"text":"cout<