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 fi='';
      fo='';
      maxn=101;
var n:longint;
    x,y,s:array[1..maxn] of longint;
    d:array[1..maxn] of real;
    free:array[1..maxn] of boolean;
    a:array[1..maxn,1..maxn] of longint;
    dist:array[1..maxn,1..maxn] of real;

procedure rf;
var i,j:longint;
begin
     read(n);
     for i:=1 to n do
     begin
          read(x[i],y[i],s[i]);
          for j:=1 to n-1 do read(a[i,j]);
     end;
     for i:=1 to n-1 do
         for j:=i+1 to n do
         begin
              dist[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
              dist[j,i]:=dist[i,j];
         end;
end;

procedure pr;
var i,x,y,j,k:longint; min:real;
begin
     for i:=1 to n do
     begin
          free[i]:=true; d[i]:=1234567890.0;
     end;
     d[1]:=0; free[1]:=false; x:=1;
     for i:=2 to n do
     begin
          j:=1;
          for k:=1 to s[x] do
          begin
               while not free[a[x,j]] and (j<=n-1) do inc(j);
               if j>n-1 then break;
               if d[a[x,j]]>d[x]+dist[a[x,j],x] then
                  d[a[x,j]]:=d[x]+dist[a[x,j],x];
               inc(j);
          end;
          min:=1234567889.0;
          for j:=1 to n do
              if free[j] and (d[j]<min) then
              begin
                   min:=d[j]; y:=j;
              end;
          free[y]:=false; x:=y;
     end;
end;

procedure wf;
var i:longint;
begin
     for i:=1 to n do writeln(d[i]:0:6);
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     rf;
     pr;
     wf;
     close(input); close(output);
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<cfloat>
#include<cmath>
#include<queue>
using namespace std;

#define N 100
int x[N], y[N], s[N], n, receive[N][N-1];
double dis[N][N], dp[N];

inline int sqr(int x) { return x*x; }

int main() {
#ifdef __DONGOCKHANH__
    freopen("input.txt", "r", stdin);
#endif
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d%d",x+i,y+i,s+i);
        for(int j = 0; j < n - 1; --receive[i][j++])
            scanf("%d", &receive[i][j]);
        dp[i] = DBL_MAX;
    }
    for(int i = 0; i < n; ++i)
        for(int j = i+1; j < n; ++j)
            dis[i][j] = dis[j][i] = sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j]));
    priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > qu;
    dp[0] = 0; qu.push(make_pair((double) 0, 0));
    while(!qu.empty()) {
        double du = qu.top().first; int u = qu.top().second; qu.pop();
        //printf("%d %.10lf\n", u+1, du);
        if(du > dp[u]) continue;
        for(int i = 0, cnt = 0; cnt < s[u] && i < n-1; ++i) {
            int v = receive[u][i];
            //printf("v: %d %.10lf %d\n", v+1, dp[v] == DBL_MAX ? -1 : dp[v], cnt);
            if(dp[v] < du) continue;
            if(du + dis[u][v] < dp[v]) qu.push(make_pair(dp[v] = du + dis[u][v], v)); 
            ++cnt;
        }
    }
    for(int i = 0; i < n; ++i) printf("%.10lf\n", dp[i]);
    return 0;
}

Code mẫu của ladpro98

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define sqr(x) ((x) * (x))
#define di pair<double, int>
#define X first
#define Y second
const int N = 110;
const double oo = 1e12;
const double eps = 1e-6;
using namespace std;
long long X[N], Y[N];
double d[N];
int S[N], adj[N][N];
bool was[N];
int n;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    REP(i, 1, n) {
        cin >> X[i] >> Y[i] >> S[i];
        FOR(j, 1, n) cin >> adj[i][j];
    }
    priority_queue <di, vector<di>, greater<di> > Q;
    REP(i, 2, n) d[i] = oo;
    Q.push(di(0.0, 1));
    while (!Q.empty()) {
        int u = Q.top().Y; double du = Q.top().X; Q.pop();
        if (fabs(du - d[u]) > eps) continue;
        was[u] = true;
        FOR(i, 1, n) {
            if (S[u] == 0) break;
            int v = adj[u][i];
            double uv = sqrt(sqr(X[u] - X[v]) + sqr(Y[u] - Y[v]));
            if (!was[v]) {
                if (d[v] > d[u] + uv) {
                    d[v] = d[u] + uv;
                    Q.push(di(d[v], v));
                }
                S[u]--;
            }
        }
    }
    REP(i, 1, n) cout << setprecision(6) << fixed << d[i] << '\n';
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=101;
  oo=1000000000000;
var
  f1,f2:text;
  a:array[1..MAXN,1..MAXN] of longint;
  time,x,y:array[1..MAXN] of double;
  fin,hpos,h,s:array[1..MAXN] of longint;
  n,hsize:longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  i,j:longint;
begin
  read(f1,n);
  for i:=1 to n do
    begin
      read(f1,x[i],y[i],s[i]);
      for j:=1 to n-1 do
        read(f1,a[i,j]);
    end;
end;
procedure ans;
var
  i:longint;
begin
  for i:=1 to n do
    writeln(f2,time[i]:0:10);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint);
var
  j:longint;
begin
  j:=i<<1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (time[h[j+1]]<time[h[j]]) then inc(j);
      if (time[h[j]]<time[h[i]]) then
        begin
          swap(hpos[h[i]],hpos[h[j]]);
          swap(h[i],h[j]);
        end;
      i:=j; j:=i<<1;
    end;
end;
procedure upHeap(i:longint);
var
  j:longint;
begin
  j:=i>>1;
  while (i>1) and (time[h[i]]<time[h[j]]) do
    begin
      swap(hpos[h[i]],hpos[h[j]]);
      swap(h[i],h[j]);
      i:=j; j:=i>>1;
    end;
end;
procedure push(u:longint);
begin
  inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
  upHeap(hsize);
end;
procedure pop(var u:longint);
begin
  u:=h[1]; hpos[u]:=1;
  swap(h[1],h[hsize]); hpos[h[1]]:=1;
  dec(hsize); downHeap(1);
end;
function dist(x1,y1,x2,y2:double):double;
begin
  dist:=sqrt(sqr(x1-x2)+sqr(y1-y2));
end;
procedure solve;
var
  count,u,v,i:longint;
begin
  hsize:=0; push(1);
  for u:=2 to n do time[u]:=oo;
  while hsize>0 do
    begin
      pop(u); count:=0; fin[u]:=1;
      for i:=1 to n-1 do
        begin
          v:=a[u,i];
          if fin[v]=0 then inc(count);
          if time[v]>time[u]+dist(x[u],y[u],x[v],y[v]) then
            begin
              time[v]:=time[u]+dist(x[u],y[u],x[v],y[v]);
              if hpos[v]=0 then push(v)
              else upHeap(hpos[v]);
            end;
          if count=s[u] then break;
        end;
    end;
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#include <cstdio>
#include <cmath>
//#include <conio.h>
#include <iostream>
#define max 10000000

using namespace std;

struct diem
{
    int x,y;
};

int n,so[110],a[110][110],flag[110];
diem d[110];
double f[110];

double min(double a,double b) { return a<b?a:b; }

double kc(diem A,diem B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

int main()
{
    //freopen("gondor.in.10","r",stdin);
    f[1] = 0;
    scanf("%d",&n);
    for(int i = 2;i<=n;i++)
        f[i] = max;
    for(int i = 1;i<=n;i++)
    {
         scanf("%d %d %d",&d[i].x,&d[i].y,&so[i]);
         for(int j = 1;j<=n-1;j++)
              scanf("%d",&a[i][j]);
    }
    memset(flag,0,sizeof(flag));
    int u = 1,fl,danhdau; flag[1] = 1; 
    while(true)
    {
         int t = 0;
         for(int i = 1;i<=n;i++)
         {
              if(!flag[a[u][i]])
              {
                  t++;
                  f[a[u][i]]=min(f[a[u][i]],f[u]+kc(d[u],d[a[u][i]]));
                  if(t==so[u])
                       break;
              }
         }
         fl = 1; double maxx = max;
         for(int i = 1;i<=n;i++)
              if(!flag[i] && f[i]<maxx)
              {
                   fl = 0;
                   danhdau = i;
                   maxx = f[i];
              }
         if(fl)
             break;
         else
         {
             flag[danhdau] = 1;
             u = danhdau;
         }
        // printf("%d\n",u);
    }
    for(int i = 1;i<=n;i++)
        printf("%lf\n",f[i]);
    //getch();               
}

Code mẫu của ll931110

{$N+} {$MODE DELPHI}
Program GONDOR;
  Const
    input  = '';
    output = '';
    maxn = 100;
    maxd = 1000000;
  Type
    rec = record
      x,y: integer;
    end;
  Var
    heap,pos,s: array[1..maxn] of integer;
    c: array[1..maxn] of rec;
    des: array[1..maxn,1..maxn] of integer;
    d: array[1..maxn] of double;
    free: array[1..maxn] of boolean;
    n,nHeap: integer;

Procedure init;
Var
  f: text;
  i,j: integer;
Begin
  Assign(f, input);
    Reset(f);

  Readln(f, n);
  For i:= 1 to n do
    Begin
      Read(f, c[i].x, c[i].y);
      Read(f, s[i]);
      For j:= 1 to n - 1 do read(f, des[i,j]);
    End;

  Close(f);
End;

Procedure update(v: integer);
Var
  parent,child: integer;
Begin
  child:= pos[v];
  If child = 0 then
    Begin
      inc(nHeap);
      child:= nHeap;
    End;

  parent:= child div 2;
  While (parent > 0) and (d[heap[parent]] > d[v]) do
    Begin
      heap[child]:= heap[parent];
      pos[heap[child]]:= child;

      child:= parent;
      parent:= child div 2;
    End;

  heap[child]:= v;
  pos[v]:= child;
End;

Function pop: integer;
Var
  r,c,v: integer;
Begin
  pop:= heap[1];
  v:= heap[nHeap];
  dec(nHeap);

  r:= 1;
  While r * 2 <= nHeap do
    Begin
      c:= r * 2;
      If (c < nHeap) and (d[heap[c + 1]] < d[heap[c]]) then inc(c);

      If d[v] <= d[heap[c]] then break;
      heap[r]:= heap[c];
      pos[heap[r]]:= r;

      r:= c;
    End;

  heap[r]:= v;
  pos[v]:= r;
End;

Procedure solve;
Var
  i,k,u,v: integer;
  tmp: double;
Begin
  Fillchar(free, sizeof(free), true);
  free[1]:= false;

  For i:= 1 to n do d[i]:= maxd;
  d[1]:= 0;

  nHeap:= 0;
  update(1);

  Repeat
    u:= pop;
    free[u]:= false;
    k:= 0;

    For i:= 1 to n - 1 do
      Begin
        v:= des[u,i];
        If free[v] then
          Begin
            inc(k);
            tmp:= sqr(c[u].x - c[v].x) + sqr(c[u].y - c[v].y);
            tmp:= sqrt(tmp);

            If d[v] > d[u] + tmp then
              Begin
                d[v]:= d[u] + tmp;
                update(v);
              End;
          End;
        If k = s[u] then break;
      End;
  Until nHeap = 0;
End;

Procedure printresult;
Var
  f: text;
  i: integer;
Begin
  Assign(f, output);
    Rewrite(f);
    For i:= 1 to n do writeln(f, d[i]:0:10);
  Close(f);
End;

Begin
  init;
  solve;
  printresult;
End.