Решение задачи №138 «Алгоритм Форда-Беллмана» с ACMP





Решение задачи №138 «Алгоритм Форда-Беллмана» с ACMP

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

Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.

Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.

Входные данные
В первой строке входного файла INPUT.TXT записаны целые числа N и M - количество вершин и количество ребер графа (1 ≤ N ≤ 100, 0 ≤ M ≤ 10000). В каждой из последующих M строк записана тройка чисел, описывающих ребра: начало ребра, конец ребра и вес (вес - целое число от -100 до 100).

Выходные данные
В выходной файл OUTPUT.TXT выведите N чисел - расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.

#include<iostream>
#define INF 30000
using namespace std;
int main(){
int n,m,i,j,k; bool f;
cin>>n>>m;
int r[m][3],d[n];
for(i=0;i<n;++i)d[i]=INF;
d[0]=0;
for(i=0;i<m;++i){
cin>>r[i][0]>>r[i][1]>>r[i][2];
r[i][0]--;r[i][1]--;}
do{f=false;
for(k=0;k<m;++k){
i=r[k][0];j=r[k][1];
if(d[i]<INF&&d[j]>d[i]+r[k][2])
{f=true;d[j]=d[i]+r[k][2];}}
}while(f);
for(auto e:d)cout<<e<<' ';
return 0;}



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