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





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

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

В ориентированном взвешенном графе вершины пронумерованы числами от 1 до N. Если i < j, то существует ребро из вершины i в вершину j, вес которого определяется по формуле:

w(i,j) = (179∙i+719∙j) mod 1000 – 500

Определите вес кратчайшего пути, ведущего из вершины 1 в вершину N.

Входные данные
Входной файл INPUT.TXT содержит целое число N (2 ≤ N ≤ 104).

Выходные данные
В выходной файл OUTPUT.TXT выведите единственное целое число – вес кратчайшего пути из вершины 1 в вершину N в описанном графе.

#include<iostream>
#define INF 30000
using namespace std;
int main(){
int n,m,i,j,k; bool f;
cin>>n;
int d[n+1];d[1]=0;
for(i=2;i<=n;++i)d[i]=INF;
do{f=false;
for(i=1;i<n;++i)
for(j=i+1;j<=n;++j){
k=(179*i+719*j)%1000-500;
if(d[i]<INF&&d[j]>d[i]+k)
{f=true;d[j]=d[i]+k;}}
}while(f);
cout<<d[n];
return 0;}



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