|
#include "stdafx.h"
#include "fstream"
using namespace std;
ifstream cin("input.txt");
ofstream cout("output.txt");
int a[101][101],c[101],v1,v2,n,m;
void p(int k, int v)
{c[k]=v;
if (v==v2 || k>=n) {
if (v==v2)
{
//for (int i=1;i<=k;i++)cout<<c[i]<<" ";cout<<endl;
int s=0;
for (int i=1;i<k;i++)s=s+a[c[i]][c[i+1]];
//cout<<"s="<<s<<endl;
if (s<m) m=s;
}
}
else
for (int i=1;i<=n;i++)
if (a[v][i]>0) p(k+1,i);
}
int main()
{int i,j,t,k;
cin>>n>>m;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)a[i][j]=0;
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;
m=10000000;
p(1,v1);
if (m>=10000000)m=-1;
cout<<m<<endl;
return 0;
}
|
program Project2;
{$APPTYPE CONSOLE}
var a:array[1..100,1..100] of integer;
smin,i,j,k,l,n,s:integer;
rez,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;
procedure p(ni,v:integer);
var s,ii:integer;
begin
c[ni]:=v;
if(ni=n)then begin
{***** 1}
s:=0;
for ii:=1 to ni-1 do s:=s+a[c[ii],c[ii+1]];
s:=s+a[c[n],c[1]];
if s<smin then begin
for ii:=1 to ni do rez[ii]:=c[ii];
smin:=s;
end;
end
else
for ii:=1 to n do
if (a[v,ii]>0)and (f(ni,ii)) then p(ni+1,ii);
end;
begin
assign(f1,'graph.dat');reset(f1);assign(f2,'graph.sol');rewrite(f2);
write('N=');
readln(n);
for i:=1 to n do
for j:=i+1 to n do begin
a[i,j]:=random(50)+1;a[j,i]:=a[i,j];
end;
smin:=maxint;
p(1,1);
close(f1);
writeln(f2,n);
for i:=1 to n do begin
for j:=1 to n-1 do
write(f2,a[i,j]:3);
writeln(f2,a[i,n]:3);
end;
writeln(f2,'-------------------');
for i:=1 to n-1 do write(f2,rez[i],' ' );
writeln(f2,rez[n] );
writeln(f2,smin);
close(f2);
end.
|
