Сайт підготовки до олімпіади з інформатики

програмування в С++

Алгоритм Форда PDF Печать E-mail
Добавил(а) Administrator   
09.10.13 22:24

 

#include "stdafx.h"

#include "fstream"

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

long a[101][101],v1,v2,n,m;

int main()

{long i,j,t,k;

cin>>n>>m;

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

for (j=1;j<=n;j++)a[i][j]=10000000;

for (k=1;k<=m;k++)

{cin>>i>>j>>t;

a[i][j]=t;a[j][i]=t;

}

cin>>v1>>v2;

/*for (i=1;i<=n;i++){

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

cout<<a[i][j]<<" ";

cout<<endl;

}

cout<<v1<<" "<<v2<<endl;

*/

for (int k=1; k<=n; k++)

for (int i=1; i<=n; i++)

for (int j=1; j<=n; j++)

a[i][j] = min (a[i][j], a[i][k] + a[k][j]);

/*for (i=1;i<=n;i++){

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

cout<<a[i][j]<<" ";

cout<<endl;

}

*/

//cout<<v1<<" "<<v2<<endl;

if (a[v1][v2]>=10000000)cout<<-1<<endl;

else  cout<<a[v1][v2]<<endl;

return 0;

}

 

program poisk_min;

{$APPTYPE CONSOLE}

var a:array[1..100,1..100] of integer;

nmin,min,i,j,k,l,n,s:integer;

c:array [1..100]of integer;

f1,f2:text;

function f(nn,vv:integer):boolean;

var pr:boolean;

i:integer;

begin

pr:=true;

for i:=1 to nn do

if vv=c[i] then pr:=false;

f:=pr;

end;

begin

assign(f1,'graph.dat');reset(f1);

assign(f2,'graph.sol');rewrite(f2);

readln(f1,n);

for i:=1 to n do

for j:=1 to n do

read(f1,a[i,j]);

close(f1);

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if a[i,k]+a[k,j]<a[i,j] then

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

for i:=1 to n do begin

for j:=1 to n do write(f2,a[i,j],' ' );

writeln(f2);

end;

close(f2);

end.

 

 

 

Статистика

Пользователей : 260
Статей : 225
Просмотрено статей : 103973

Вход/Регистрация

Нет