Editorial for TRIP
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const maxn=15; fi=''; fo=''; maxc=66000; var n,re:longint; a:array[0..maxn,0..maxn] of longint; f:array[0..maxc,0..maxn] of longint; p:array[0..maxn] of longint; procedure rf; var i,j:byte; begin assign(input,fi); reset(input); readln(n); dec(n); for i:=0 to n do begin for j:=0 to n do read(a[i,j]); readln; end; close(input); end; procedure init; var i:byte; begin p[0]:=1; for i:=1 to n+1 do p[i]:=p[i-1]*2; end; function out(j,s:longint):boolean; begin s:=(s shr j) and 1; out:=(s=0); end; function min(a,b:longint):longint; begin if a<b then min:=a else min:=b; end; procedure pr; var i,j,s,t,max:longint; begin init; max:=p[n+1]-1; for i:=0 to max do for j:=0 to n do f[i,j]:=1000000; for i:=0 to n do f[p[i],i]:=0; for s:=1 to max do for i:=0 to n do if not out(i,s) then for j:=0 to n do if out(j,s) then begin t:=s or p[j]; f[t,j]:=min(f[t,j],f[s,i]+a[i,j]); end; re:=1000000; for i:=0 to n do if f[max,i]<re then re:=f[max,i]; end; procedure wf; begin assign(output,fo); rewrite(output); write(re); close(output); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include <cstdio> #define INF 1000000000 int f[80000][20], a[20][20], n; int min( int a, int b ) { return a < b ? a : b; } int F( int mask, int end ) { if ( mask == 0 ) return 0; int & res = f[mask][end]; if ( res == 0 ) { res = INF; for( int i = 0; i < n; ++i ) if ( mask & ( 1 << i ) ) res = min( res, F(mask & ~( 1 << i ), i) + a[i][end] ); } return res; } int main() { scanf( "%d", &n ); for( int i = 0; i < n; ++i ) for( int j = 0; j < n; ++j ) scanf( "%d", &a[i][j] ); int res = INF; for( int i = 0; i < n; ++i ) res = min(res, F((1<<n)-1, i)); printf( "%d\n", res ); return 0; }
Code mẫu của ladpro98
program lem3;//dp; uses math; const fi=''; oo=1000000; maxN=15; var c:array[1..maxN,1..maxN] of longint; f:array[1..maxN,0..(1 shl maxN)] of longint; pow:array[0..maxN] of longint; n:longint; procedure input; var inp:text; i,j:longint; begin assign(inp,fi); reset(inp); readln(inp,n); for i:=1 to n do for j:=1 to n do read(inp,c[i,j]); close(inp); end; function getbit(i,j:longint):longint; begin exit(i shr (j-1) and 1); end; procedure init; var i:longint; begin pow[0]:=1; for i:=1 to n do pow[i]:=pow[i-1] shl 1; end; procedure dp; var i,j,k:longint; begin for j:=1 to pow[n]-1 do for i:=1 to n do begin f[i,j]:=oo; for k:=1 to n do if k<>i then if getbit(j,k)=1 then f[i,j]:=min(f[i,j],f[k,j-pow[k-1]]+c[k,i]); end; end; procedure output; var i,j,res:longint; begin res:=oo; for i:=1 to n do res:=min(res,f[i,pow[n]-1-pow[i-1]]); write(res); end; begin input; init; dp; output; end.
Code mẫu của RR
{$R-,Q-} uses math; const FINP=''; FOUT=''; MAXN=15; oo=1000000; var t,n:longint; c:array[1..MAXN,1..MAXN] of longint; d:array[1..32767,1..15] of longint; procedure inp; inline; var f:text; i,j:longint; begin assign(f,FINP); reset(f); read(f,n); for i:=1 to n do for j:=1 to n do read(f,c[i,j]); t:=1 shl n-1; close(f); end; procedure ans; inline; var f:text; kq,i:longint; begin assign(f,FOUT); rewrite(f); kq:=oo; for i:=1 to n do kq:=min(kq,d[t,i]); writeln(f,kq); close(f); end; procedure solve; inline; var i,j,ii,jj:longint; begin for i:=1 to t do for j:=1 to n do d[i,j]:=oo; for i:=1 to n do d[1 shl (i-1),i]:=0; for i:=1 to t do for j:=1 to n do if (i shr (j-1)) and 1=1 then begin ii:=i and (not (1 shl (j-1))); for jj:=1 to n do if (ii shr (jj-1)) and 1=1 then d[i,j]:=min(d[i,j],d[ii,jj]+c[jj,j]); end; end; begin inp; solve; ans; end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> int f[70000][17]; int main() { // freopen("LEM3.in","r",stdin); int n, a[17][17],b[17],chay=1; scanf("%d",&n); for(int i = 0;i<n;i++) for(int j = 0;j<n;j++) scanf("%d",&a[i][j]); for(int i = 0;i<n;i++) f[0][i] = 0; b[0] = 1; for(int i = 1;i<n;i++) { b[i] = b[i-1]*2; chay = chay + b[i]; } for(int i = 1;i<=chay;i++) { int t[n],m= i; for(int j = 0;j<n;j++) { t[j] = m%2; m = m/2; } for(int j = 0;j<n;j++) { if(t[j]==0) f[i][j]=0; else { int min = 1000000; for(int k = 0;k<n;k++) if(f[i-b[j]][k]+a[k][j] < min && t[k]!=0 && k!=j) min = f[i-b[j]][k]+a[k][j]; if(min == 1000000) f[i][j] = 0; else f[i][j] = min; } } } int Min = 1000000; for(int i = 0;i<n;i++) if(f[chay][i]<Min) Min =f[chay][i]; printf("%d",Min); // getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program LEM3; Const input = ''; output = ''; max = 32767; Var d: array[0..16] of integer; a: array[1..16,1..16] of integer; F: array[0..max,1..16] of integer; n: integer; Procedure init; Var fi: text; i,j: integer; Begin Assign(fi, input); Reset(fi); Readln(fi, n); For i:= 1 to n do For j:= 1 to n do read(fi, a[i,j]); Close(fi); End; Procedure power; Var i: integer; Begin d[0]:= 1; For i:= 1 to n do d[i]:= d[i - 1] shl 1; End; Procedure optimize; Var i,j,k,t,tmp: integer; Begin For i:= 0 to d[n] - 1 do For j:= 1 to n do F[i,j]:= 1000000000; Fillchar(F[0], sizeof(F[0]), 0); For i:= 1 to n do F[d[i - 1],i]:= 0; For i:= 0 to d[n] - 1 do For j:= 1 to n do if i and d[j - 1] = d[j - 1] then Begin t:= i - d[j - 1]; For k:= 1 to n do if t and d[k - 1] = d[k - 1] then Begin tmp:= F[t,k] + a[k,j]; IF F[i,j] > tmp then F[i,j]:= tmp; End; End; End; Procedure printresult; Var fo: text; i,val: integer; Begin Assign(fo, output); Rewrite(fo); val:= F[d[n] - 1,1]; For i:= 2 to n do if val > F[d[n] - 1,i] then val:= F[d[n] - 1,i]; Writeln(fo, val); Close(fo); End; Begin init; power; optimize; printresult; End.
Code mẫu của skyvn97
#include<stdio.h> #define INF 1e9 #define MAX 22 int c[MAX][MAX]; int f[MAX][100100]; int n; void init(void) { int i,j; scanf("%d",&n); for (i=1;i<=n;i=i+1) for (j=1;j<=n;j=j+1) scanf("%d",&c[i][j]); for (i=1;i<=n;i=i+1) for (j=0;j<(1<<n);j=j+1) f[i][j]=INF; } int r(int i,int s) { if ((s|(1<<(i-1)))!=s) return (INF); if (s==(1<<(i-1))) return (0); if (f[i][s]<INF) return (f[i][s]); int j,t; for (j=1;j<=n;j=j+1) if ((i!=j) && ((s|(1<<(j-1)))==s)) { t=r(j,s&((1<<n)-1-(1<<(i-1))))+c[j][i]; if (f[i][s]>t) f[i][s]=t; } return (f[i][s]); } void process(void) { int m=INF; int i; for (i=1;i<=n;i=i+1) if (m>r(i,(1<<n)-1)) m=r(i,(1<<n)-1); printf("%d",m); } int main(void) { init(); process(); }
Code mẫu của khuc_tuan
#include <iostream> using namespace std; int n, c[20][20], f[1<<17][20]; int main() { cin >> n; for(int i=0;i<n;++i) for(int j=0;j<n;++j) cin >> c[i][j]; memset( f, 0x1f, sizeof(f)); for(int i=0;i<n;++i) f[1<<i][i] = 0; for(int b=1;b<(1<<n);++b) for(int i=0;i<n;++i) for(int j=0;j<n;++j) if((b&(1<<j))==0) f[b|(1<<j)][j] <?= f[b][i] + c[i][j]; cout << *min_element(f[(1<<n)-1], f[(1<<n)-1]+n) << endl; return 0; }
Comments