Hướng dẫn giải của Xây dựng đường
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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 ladpro98
program qbbuild; uses math; const oo=high(longint); fi=''; maxn=105; var n,m,res:longint; d:array[1..maxn,1..maxn] of longint; s:array[1..4] of longint; procedure input; var inp:text; i,j,x,y,w:longint; begin assign(inp,fi); reset(inp); readln(inp,n); readln(inp,s[1],s[2],s[3],s[4]); for i:=1 to n do for j:=1 to n do begin if i=j then d[i,j]:=0 else d[i,j]:=oo; end; while not eof(inp) do begin readln(inp,x,y,w); if d[x,y]>w then begin d[x,y]:=w; d[y,x]:=w; end; end; close(inp); end; procedure floyd; var i,j,k:longint; begin for k:=1 to n do for i:=1 to n do if d[i,k]<oo then for j:=1 to n do if d[k,j]<oo then begin if d[i,j]>d[i,k]+d[k,j] then d[i,j]:=d[i,k]+d[k,j]; end; end; procedure output; var I,J,p,q,r,T,sum:longint; begin res:=oo; for i:=1 to n do for j:=i to n do begin for p:=1 to 4 do for q:=1 to 4 do for r:=1 to 4 do for t:=1 to 4 do if (p*q*r*t=24) and (p+q+r+t=10) then res:=min(res,d[i,s[p]]+d[i,s[q]]+d[j,s[r]]+d[j,s[t]]+d[i,j]); end; write(res); end; begin input; floyd; output; end.
Code mẫu của RR
#include <iomanip> #include <sstream> #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair using namespace std; const double PI = acos(-1.0); #define TWO(x) (1<<(x)) #define CONTAIN(S,x) (S & TWO(x)) int n, m, k; int f[111][222], mark[111]; vector< pair<int,int> > ke[111]; set< pair<int, pair<int,int> > > s; int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); scanf("%d", &n); k = 4; FOR(i,1,n) REP(mask,TWO(k)) f[i][mask] = 1000111000; FOR(i,1,k) { int u; scanf("%d", &u); mark[u] = i; f[u][TWO(i-1)] = 0; s.insert(MP(0,MP(u,TWO(i-1)))); } int u, v, c; while (scanf("%d%d%d", &u, &v, &c) == 3) { ke[u].PB(MP(v,c)); ke[v].PB(MP(u,c)); } while (!s.empty()) { int l = s.begin()->F; pair<int,int> now = s.begin()->S; int u = now.F, mask = now.S; if (now.S == TWO(k) - 1) { printf("%d\n", l); return 0; } s.erase(s.begin()); // cout << u << ' ' << mask << endl; REP(i,ke[u].size()) { int v = ke[u][i].F, c = ke[u][i].S; int mask2 = now.S; if (mark[v]) mask2 |= TWO(mark[v] - 1); int cost = f[u][mask] + c; if (f[v][mask2] > cost) { f[v][mask2] = cost; s.insert(MP(f[v][mask2], MP(v, mask2))); } REP(mask3,TWO(k)) if ((mask3 & mask) == 0) { int cost = f[u][mask] + f[v][mask3] + c; if (f[v][mask3 | mask] > cost) { f[v][mask3 | mask] = cost; s.insert(MP(cost, MP(v, mask3 | mask))); } } } } return 0; }
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> #define max 101 #define maxEC 50000 #define maxC max*maxEC long c[max][max],Trace[max][max],n,a[5],min=maxC; void Enter() { long u,v,x; scanf("%ld",&n); for(long i=1;i<=4;i++) scanf("%ld",&a[i]); for(u=1;u<=n;u++) for(v=1;v<=n;v++) { if(u==v) c[u][v]=0; else c[u][v]=maxC; } while(scanf("%ld %ld %ld",&u,&v,&x)>0&&x>0) { if(c[u][v]>x) { c[u][v]=x; c[v][u]=x; } } } void Floyd() { for(long u=1;u<=n;u++) for(long v=1;v<=n;v++) Trace[u][v]=v; for(long k=1;k<=n;k++) for(long u=1;u<=n;u++) for(long v=1;v<=n;v++) if(c[u][v]>c[u][k]+c[k][v]) { c[u][v]=c[u][k]+c[k][v]; Trace[u][v]=Trace[u][k]; } } void xuli() { for(long i=1;i<=n;i++) for(int j = 1;j<=n;j++) { long mini=c[a[1]][i]+c[a[2]][i]+c[i][j]+c[a[3]][j]+c[a[4]][j]; if(mini<min) min=mini; //printf("%ld ",mini); } for(long i=1;i<=n;i++) for(int j = 1;j<=n;j++) { long mini=c[a[1]][i]+c[a[4]][i]+c[i][j]+c[a[3]][j]+c[a[2]][j]; if(mini<min) min=mini; //printf("%ld ",mini); } for(long i=1;i<=n;i++) for(int j = 1;j<=n;j++) { long mini=c[a[1]][i]+c[a[3]][i]+c[i][j]+c[a[4]][j]+c[a[2]][j]; if(mini<min) min=mini; //printf("%ld ",mini); } printf("%ld",min); } main() { Enter(); Floyd(); xuli(); //getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program QBBUILD; Const input = ''; output = ''; maxn = 100; maxc = 100000000; maxd = 4; Var c: array[1..maxn,1..maxn] of integer; a: array[1..maxd] of integer; n,res: integer; Procedure LoadGraph; Var f: text; i,j,k,u,v: integer; Begin Assign(f, input); Reset(f); Readln(f, n); For i:= 1 to n do For j:= 1 to n do if i = j then c[i,j]:= 0 else c[i,j]:= maxc; Readln(f, a[1], a[2], a[3], a[4]); While not Eof(f) do Begin Readln(f, u, v, k); If c[u,v] > k then Begin c[u,v]:= k; c[v,u]:= k; End; End; Close(f); End; Procedure Floyd; Var u,v,k: integer; Begin For k:= 1 to n do For u:= 1 to n do For v:= 1 to n do if c[u,v] > c[u,k] + c[k,v] then c[u,v]:= c[u,k] + c[k,v]; End; Procedure solve; Var f: text; i,j,tmp: integer; Begin res:= maxc; For i:= 1 to n do For j:= 1 to n do Begin tmp:= c[i,a[1]] + c[i,a[2]] + c[j,a[3]] + c[j,a[4]]; If tmp > c[i,a[1]] + c[i,a[3]] + c[j,a[2]] + c[j,a[4]] then tmp:= c[i,a[1]] + c[i,a[3]] + c[j,a[2]] + c[j,a[4]]; If tmp > c[i,a[1]] + c[i,a[4]] + c[j,a[2]] + c[j,a[3]] then tmp:= c[i,a[1]] + c[i,a[4]] + c[j,a[2]] + c[j,a[3]]; tmp:= tmp + c[i,j]; If res > tmp then res:= tmp; End; Assign(f, output); Rewrite(f); Writeln(f, res); Close(f); End; Begin LoadGraph; Floyd; solve; End.
Code mẫu của khuc_tuan
#include <iostream> using namespace std; int n; int id[4]; int a[101][101]; int inf; int main() { scanf("%d", &n); for(int i=0;i<4;++i) scanf("%d", &id[i]); inf = 1000000000; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j) a[i][j] = inf; else a[i][j] = 0; { int u, v, c; while(scanf("%d%d%d", &u, &v, &c)!=EOF) { a[u][v] <?= c; a[v][u] <?= c; } } for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[i][j] <?= a[i][k] + a[k][j]; int result = inf; sort( id, id+4); do { for(int u=1;u<=n;++u) for(int v=1;v<=n;++v) result <?= a[u][id[0]] + a[u][id[1]] + a[v][id[2]] + a[v][id[3]] + a[u][v]; } while(next_permutation(id,id+4)); printf("%d\n", result); return 0; }
Bình luận