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.

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

Please read the guidelines before commenting.


There are no comments at the moment.