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=150;
      maxm=30000;
      maxc=2000000000;
var cnt,n,m:longint;
    re:int64;
    b:array[1..maxm,0..2] of integer;
    a:array[1..maxn,1..maxn] of int64;
    tr:array[1..maxn,1..maxn] of byte;
    d:array[1..maxm] of byte;
    arc:array[1..maxn,1..maxn] of integer;

procedure rf;
var i,j:longint;
begin
     fillchar(d,sizeof(d),0);
     fillchar(arc,sizeof(arc),0);
     readln(n,m);
     for i:=1 to n do
         for j:=1 to n do
             if i<>j then a[i,j]:=maxc else a[i,j]:=0;
     for i:=1 to m do
     begin
          readln(b[i,0],b[i,1],b[i,2]);
          if a[b[i,0],b[i,1]]>b[i,2] then
          begin
               a[b[i,0],b[i,1]]:=b[i,2];
               arc[b[i,0],b[i,1]]:=i;
               d[i]:=1;
          end;
          if a[b[i,1],b[i,0]]>b[i,2] then
          begin
               a[b[i,1],b[i,0]]:=b[i,2];
               arc[b[i,1],b[i,0]]:=i;
               d[i]:=1;
          end;
     end;
end;

procedure trace(s,f:byte);
var j:longint;
begin
     if s=f then exit;
     repeat
           j:=tr[s,f];
           d[arc[s,j]]:=2;
           s:=j;
     until s=f;
end;

procedure pr;
var i,j,k,t:longint;
begin
     for i:=1 to n do
         for j:=1 to n do
             tr[i,j]:=j;
     for i:=1 to n do
         for j:=1 to n do
             for k:=1 to n do
                 if a[j,k]>a[j,i]+a[i,k] then
                 begin
                      a[j,k]:=a[j,i]+a[i,k];
                      tr[j,k]:=tr[j,i];
                 end;
     re:=maxc-10; 
     for i:=1 to n do
         if a[1,i]+a[2,i]+a[3,i]<re then
         begin
              t:=i;
              re:=a[1,i]+a[2,i]+a[3,i];
         end;
     for i:=1 to 3 do trace(i,t);
end;

procedure wf;
var i:longint;
begin
     writeln(re); cnt:=0;
     for i:=1 to m do
         if d[i]=2 then inc(cnt);
     writeln(cnt);
     for i:=1 to m do
    if d[i]=2 then write(i,' ');
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<cstring>

const int N = 100, M = 20000;
int c[N][N], n, m, id[N][N], t[N][N];
bool choose[M];

void reset() {
    memset(c, 0x3f, sizeof c);
    memset(id, -1, sizeof id);
    memset(t, -1, sizeof t);
}

void enter() {
    scanf("%d%d",&n,&m);
    for(int i = 0; i < m; ++i) {
        int u, v, l;
        scanf("%d%d%d",&u,&v,&l); --u; --v;
        if(l < c[u][v]) {
            c[u][v] = c[v][u] = l;
            id[u][v] = id[v][u] = i;
            t[u][v] = v; t[v][u] = u;
        }
    }
    for(int u = 0; u < n; ++u) c[u][u] = 0;
}

void floyd() {
    for(int k = 0; k < n; ++k)
        for(int u = 0; u < n; ++u)
            for(int v = 0; v < n; ++v)
                if(c[u][v] > c[u][k] + c[k][v]) {
                    c[u][v] = c[u][k] + c[k][v];
                    t[u][v] = t[u][k];
                }
}

void trace(int u, int v) {
    while(u != v) {
        choose[id[u][t[u][v]]] = true;
        u = t[u][v];
    }
}

void solve() {
    int u = 0;
    for(int v = 1; v < n; ++v)
        if(c[0][v] + c[1][v] + c[2][v] < c[0][u] + c[1][u] + c[2][u])
            u = v;

    trace(0, u); trace(1, u); trace(2, u);
    int k = 0; for(int i = 0; i < m; ++i) if(choose[i]) ++k;
    printf("%d\n%d\n", c[0][u] + c[1][u] + c[2][u], k);
    for(int i = 0, c = 0; i < m; ++i) if(choose[i]) {
        if(c++) printf(" ");
        printf("%d", i+1);
    }
    printf("\n");
}

int main() {
    reset();
    enter();
    floyd();
    solve();
    return 0;
}

Code mẫu của ladpro98

program three;
const   maxn=111;
        oo=123456789;
        fi='';
var     n,m,st,d,res:longint;
        edge,trace,w:array[1..maxn,1..maxn] of longint;
        kq:array[1..maxn*maxn] of longint;

procedure input;
var     inp:text;
        i,j,x,y,v:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,m);
        for i:=1 to n do
        for j:=1 to n do
        if i=j then w[i,j]:=0
        else    w[i,j]:=oo;
        for i:=1 to m do
        begin
                readln(inp,x,y,v);
                if w[x,y]>v then
                begin
                        w[x,y]:=v;
                        w[y,x]:=v;
                        edge[x,y]:=i;
                        edge[y,x]:=i;
                end;
        end;
        close(inp);
end;

procedure Floyd;
var     i,j,k:longint;
begin
        for i:=1 to n do
        for j:=1 to n do
        trace[i,j]:=j;
        for k:=1 to n do
        for i:=1 to n do
        if w[i,k]<oo then
        for j:=1 to n do
        if w[j,k]<oo then
        if w[i,j]>w[i,k]+w[k,j] then
        begin
                w[i,j]:=w[i,k]+w[k,j];
                trace[i,j]:=trace[i,k];
        end;
end;

procedure truy(i:longint);
var     u:longint;
begin
        u:=st;
        while u<>i do
        begin
                inc(d);
                kq[d]:=edge[u,trace[u,i]];
                u:=trace[u,i];
        end;
end;

procedure output;
var     i:longint;
begin
        res:=oo;
        for i:=1 to n do
        if res>w[i,1]+w[i,2]+w[i,3] then
        begin
                res:=w[i,1]+w[i,2]+w[i,3];
                st:=i;
        end;
        writeln(res);
        for i:=1 to 3 do truy(i);
        writeln(d);
        for i:=1 to d do
        write(kq[i],' ');
end;

begin
        input;
        Floyd;
        output;
end.

Code mẫu của RR

var
  cc,tmp,res,i,j,k,n,m:longint;
  trace,ind,c:array[1..111,1..111] of longint;
  cnt:longint;
  a:array[1..100111] of longint;

procedure sort(l,r:longint);
    var
      i,j,mid,tmp:longint;
    begin
      i:=l; j:=r; mid:=a[l+random(r-l+1)];
      repeat
        while a[i]<mid do inc(i);
        while a[j]>mid do dec(j);
        if i<=j then
          begin
            tmp:=a[i]; a[i]:=a[j]; a[j]:=tmp;
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
    end;

begin
  read(n,m);

  for i:=1 to n do
  for j:=1 to n do
    c[i,j]:=1000111000;

  for k:=1 to m do
    begin
      read(i,j,cc);
      if cc<c[i,j] then
        begin
          c[i,j]:=cc;
          c[j,i]:=cc;
          ind[i,j]:=k;
          ind[j,i]:=k;
        end;
    end;

  for i:=1 to n do c[i,i]:=0;

  for i:=1 to n do
  for j:=1 to n do
    trace[i,j]:=j;

  for k:=1 to n do
    for i:=1 to n do
    for j:=1 to n do
      if c[i,k]+c[k,j]<c[i,j] then
        begin
          c[i,j]:=c[i,k]+c[k,j];
          trace[i,j]:=trace[i,k];
        end;

  k:=1; res:=1000111000;
  for j:=1 to n do
    begin
      tmp:=c[j,1]+c[j,2]+c[j,3];
      if tmp<res then
        begin
          res:=tmp;
          k:=j;
        end;
    end;

  writeln(res);

  tmp:=k;
  while k<>1 do
    begin
      inc(cnt);
      a[cnt]:=ind[k,trace[k,1]];
      k:=trace[k,1];
    end;

  k:=tmp;
  while k<>2 do
    begin
      inc(cnt);
      a[cnt]:=ind[k,trace[k,2]];
      k:=trace[k,2];
    end;

  k:=tmp;
  while k<>3 do
    begin
      inc(cnt);
      a[cnt]:=ind[k,trace[k,3]];
      k:=trace[k,3];
    end;

  sort(1,cnt);
  tmp:=1;
  for i:=2 to cnt do
  if a[i]>a[i-1] then
    begin
      inc(tmp);
      a[tmp]:=a[i];
    end;

  writeln(tmp);
  for i:=1 to tmp do write(a[i],' ');
  writeln;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#define max 1000
#define maxEC 10000
#define maxC max*maxEC
long c[max][max],Trace[max][max],n,x,f[max][max];
void Enter()
{  
long m,u,v;
scanf("%ld %ld",&n,&m);
for(long u=1;u<=n;u++)
  for(long v=1;v<=n;v++)
    {
    if(u==v) c[u][v]=0;
    else c[u][v]=maxC;
    }
for(long i=1;i<=m;i++)
  {
  scanf("%ld %ld",&u,&v);
  scanf("%ld",&x);
  if(x<c[u][v])
    {
    c[v][u]=x;  c[u][v]=x;
    f[u][v]=i;  f[v][u]=i;
    }
  }
}
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 Result()
{
long min=maxC*3,t[4];
for(long i=1;i<=n;i++)
  if(min>c[1][i]+c[2][i]+c[3][i])
    {
    min=c[1][i]+c[2][i]+c[3][i];
    x=i;
    }
for(long i=1;i<=3;i++)
  {
  t[i]=0;
  long k=i;
  while(k!=x)
    {
    t[i]++;
    k=Trace[k][x];
    }
  }
printf("%ld\n%ld\n",min,t[1]+t[2]+t[3]);
for(long i=1;i<=3;i++)
  {
  long k=i;
  while(k!=x)
    {
    printf("%ld ",f[k][Trace[k][x]]);
    k=Trace[k][x];
    }
  }           
}     
main()
{
Enter();
Floyd();
Result();
//getch();
}

Code mẫu của ll931110

Program THREE;
        Type
                rec = record
                        cost: int64;
                        edge: longint;
                End;
        Var
                    c: array[1..100,1..100] of rec;
                trace: array[1..100,1..100] of longint;
                  n,m: longint;

Procedure LoadGraph;
          Var
                i,u,v,k: longint;
          Begin
                Readln(n, m);

                Fillchar(c, sizeof(c), 0);
                For u:= 1 to n do
                    For v:= 1 to n do if u = v then c[u,v].cost:= 0
                                               else c[u,v].cost:= high(longint);

                For i:= 1 to m do
                        Begin
                                Readln(u, v, k);
                                If c[u,v].cost > k then
                                        Begin
                                                c[u,v].cost:= k;        c[u,v].edge:= i;
                                                c[v,u].cost:= k;        c[v,u].edge:= i;
                                        End;
                        End;
          End;

Procedure Floyd;
          Var
                k,u,v: longint;
          Begin
                For u:= 1 to n do
                    For v:= 1 to n do trace[u,v]:= v;

                For k:= 1 to n do
                    For u:= 1 to n do
                        For v:= 1 to n do
                                if c[u,v].cost > c[u,k].cost + c[k,v].cost then
                                        Begin
                                                c[u,v].cost:= c[u,k].cost + c[k,v].cost;
                                                trace[u,v]:= trace[u,k];
                                        End;
          End;

Procedure solve;
          Var
                  kc,num,k,x,i: longint;
                           arr: array[1..20000] of longint;
          Begin
                        kc:= c[1,1].cost + c[2,1].cost + c[3,1].cost;
                        k:= 1;

                        For x:= 2 to n do
                                If kc > c[1,x].cost + c[2,x].cost + c[3,x].cost then
                                        Begin
                                                kc:= c[1,x].cost + c[2,x].cost + c[3,x].cost;
                                                k:= x;
                                        End;
                        Writeln(kc);

                        num:= 0;
                        For i:= 1 to 3 do
                                Begin
                                        x:= i;
                                        While x <> k do
                                                Begin
                                                        inc(num);
                                                        arr[num]:= c[x,trace[x,k]].edge;
                                                        x:= trace[x,k];
                                                End;
                                End;

                        Writeln(num);
                        For i:= 1 to num do write(arr[i], ' ');
          End;

Begin
        LoadGraph;
        Floyd;
        solve;
End.

Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#include<queue>
#define MAXV   111
#define MAXE   20202
#define INF   1e9
#define w   first
#define v   second
using namespace std;
typedef pair<int,int> ii;
vector<ii> g[MAXV];
ii a[MAXV][MAXV];
bool r[MAXE];
int d[7][MAXV];
int t[7][MAXV];
int m,n,c;
void loadgraph(void) {
    int i,j,u,v,c;
    scanf("%d",&n);
    scanf("%d",&m); 
    for (i=1;i<=n;i=i+1)
        for (j=1;j<=n;j=j+1)
            a[i][j]=ii(INF,m+1);    
    for (i=1;i<=m;i=i+1) {
        r[i]=false;
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%d",&c);
        a[u][v]=min(a[u][v],ii(c,i));
        a[v][u]=min(a[v][u],ii(c,i));
    }
    for (i=1;i<=n;i=i+1)
        for (j=1;j<=n;j=j+1)
            if (a[i][j].w<INF) g[i].push_back(ii(a[i][j].w,j));
    for (i=1;i<4;i=i+1)
        for (j=1;j<=n;j=j+1)
            d[i][j]=INF;
}
void dijkstra(int s) {
    priority_queue<ii,vector<ii>,greater<ii> > q;
    while (!q.empty()) q.pop();
    int i,u,w;
    ii p;
    q.push(ii(0,s));
    d[s][s]=0;
    while (!q.empty()) {
        p=q.top();q.pop();
        u=p.v;
        w=p.w;
        for (i=0;i<g[u].size();i=i+1)
            if (w+g[u][i].w<d[s][g[u][i].v]) {
                d[s][g[u][i].v]=w+g[u][i].w;
                t[s][g[u][i].v]=u;
                q.push(ii(w+g[u][i].w,g[u][i].v));
            }
    }
}
void trace(int s,int f) {
    int i;
    i=f;
    while (true) {
        if (i==s) return;
        r[a[t[s][i]][i].v]=true;
        c++;
        i=t[s][i];
    }
}
void process(void) {
    int s,i,j,u;
    for (i=1;i<4;i=i+1) dijkstra(i);
    s=INF;
    for (i=1;i<=n;i=i+1)
        if (s>d[1][i]+d[2][i]+d[3][i]) {
            s=d[1][i]+d[2][i]+d[3][i];
            u=i;
        }
    c=0;
    for (i=1;i<4;i=i+1) trace(i,u);
    printf("%d\n%d\n",s,c);
    j=0;
    for (i=1;i<=m;i=i+1) 
        if (r[i]) {
            printf("%d",i);
            j++;
            if (j<c) printf(" ");
        }
}
int main(void) {
    loadgraph();
    process();
    return 0;
}

Code mẫu của khuc_tuan

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

#define maxn 111

int n, m;
int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn],d[maxn][maxn];

void truyvet(int i,int j) {
    if(i==j) return;
    if(b[i][j]==0) {
        c[i][j]=c[j][i]=1; 
        return;
    }    
    truyvet( i, b[i][j]);
    truyvet( j, b[i][j]);
}    

int main() {
    scanf("%d%d", &n, &m);
    memset( a, 0x1f, sizeof(a));
    for(int i=1;i<=n;++i) a[i][i]=0;
    for(int i=1;i<=m;++i) {
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        if(a[u][v]>c) {
            a[u][v]=a[v][u]=c;
            d[u][v]=d[v][u]=i;
        }    
    }    
    for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) {
        if(a[i][j]>a[i][k]+a[k][j]) {
            a[i][j]=a[j][i]=a[i][k]+a[k][j];
            b[i][j]=b[j][i]=k;
        }    
    }    
    int minl = 1000000000, imin = -1;
    for(int i=1;i<=n;++i) if(a[1][i]+a[2][i]+a[3][i]<=minl) {
        minl = a[1][i]+a[2][i]+a[3][i];
        imin = i;
    }    
    printf("%d\n",minl);
    truyvet(imin,1);
    truyvet(imin,2);
    truyvet(imin,3);
    int res=0;
    for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(c[i][j]) ++res;
    printf("%d\n", res);
    for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(c[i][j]) printf("%d ", d[i][j]);
    return 0;
}