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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.