Editorial for Xây dựng đường
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 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; }
Comments