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

uses math;
const fi='';
      oo=1000000;
var n,m,xx,yy,i,j,k:longint;
    a:array[1..1000,1..1000] of boolean;
    x,y:array[1..1000] of longint;
    d:array[1..1000] of real;
    free:array[1..1000] of boolean;
    z,zz,mn:real;

function calc(u,v:longint):real;
var t,tt:real;
begin
        t:=x[u]-x[v]; tt:=y[u]-y[v];
        calc:=sqrt(t*t+tt*tt);
end;

begin
        assign(input,fi); reset(input);
        read(n,m,z);
        for i:=1 to n do read(x[i],y[i]);
        for i:=1 to m do
        begin
                read(xx,yy);
                a[xx,yy]:=true; a[yy,xx]:=true;
        end;
        for i:=1 to n do
        begin
                free[i]:=true;
                d[i]:=oo;
        end;
        free[1]:=false; d[1]:=0; xx:=1;
        repeat
              for j:=1 to n do
                 if free[j] then
                 begin
                      if a[xx,j] then d[j]:=d[xx]
                      else
                      begin
                           zz:=calc(xx,j);
                           if zz<=z then d[j]:=min(d[j],d[xx]+zz);
                      end;
                 end;
              k:=0;  mn:=oo;
              for j:=1 to n do
                if free[j] and (d[j]<mn) then
                begin
                        mn:=d[j]; k:=j;
                end;
              if k=0 then break;
              xx:=k; free[xx]:=false;
        until not free[n];
        if free[n] then writeln(-1)
        else writeln(trunc(d[n]*1000));
        close(input);
end.

Code mẫu của happyboy99x

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

const int N = 1000 + 5;
const double EPS = 1e-6;
typedef pair<double, int> di;

double d[N][N], m, dd[N];
bool rem[N][N];
int n, x[N], y[N], w;

void enter() {
    scanf("%d%d%lf", &n, &w, &m);
    for(int i = 0; i < n; ++i) scanf("%d%d", x+i, y+i);
    for(int i = 0, u, v; i < w; ++i) {
        scanf("%d%d", &u, &v); --u; --v;
        rem[u][v] = rem[v][u] = 1;
    }
}

double sqr(const double &x) { return x * x; }

void solve() {
    for(int i = 0; i < n; ++i) {
        d[i][i] = 1000000000;
        for(int j = i + 1; j < n; ++j)
            if(rem[i][j] == 0) {
                double v = sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j]));
                d[i][j] = d[j][i] = v + EPS < m ? v : 1000000000;
            }
        dd[i] = 1000000000;
    }
    priority_queue<di, vector<di>, greater<di> > q; q.push(di(0, 0)); dd[0] = 0;
    while(!q.empty()) {
        double du = q.top().first; int u = q.top().second; q.pop();
        if(du > dd[u] + EPS) continue;
        for(int v = 0; v < n; ++v) if(dd[v] > du + d[u][v] + EPS)
            q.push(di(dd[v] = du + d[u][v], v));
    }
    printf("%d\n", dd[n-1] >= 1000000000 ? -1 : int(dd[n-1] * 1000));
}

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

Code mẫu của ladpro98

{$MODE OBJFPC}
program pwrfail;
uses    math;
type    e=record
        x,y:int64;
        end;
        e2=record
        v:longint;
        w:extended;
        end;
const   maxn=1010;
        fi='';
var     a:array[1..maxn] of e;
        pos,h,len:array[1..maxn] of longint;
        d:array[1..maxn] of extended;
        cn:array[1..maxn,1..maxn] of boolean;
        c:array[1..maxn,1..maxn] of e2;
        n,w,nh:longint;
        m:extended;

procedure input;
var     inp:text;
        i,x,y,j:longint;
        temp:extended;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,w);
        readln(inp,m);
        for i:=1 to n do
        readln(inp,a[i].x,a[i].y);
        for i:=1 to w do
        begin
                readln(inp,x,y);
                cn[x,y]:=true;
                cn[y,x]:=true;
        end;
        for i:=1 to n do
        begin
                len[i]:=0;
                for j:=1 to n do
                if j<>i then
                begin
                        if cn[i,j] then
                        begin
                                inc(len[i]);
                                c[i,len[i]].v:=j;
                                c[i,len[i]].w:=0;
                                continue;
                        end;
                        temp:=sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y));
                        if temp<=M then
                        begin
                                inc(len[i]);
                                c[i,len[i]].v:=j;
                                c[i,len[i]].w:=temp;
                        end;
                end;
        end;

        close(inp);
end;

procedure update(v:longint);
var     p,c:longint;
begin
        c:=pos[v];
        if c=0 then
        begin
                inc(nh);
                c:=nh;
        end;
        repeat
                p:=c shr 1;
                if (p=0) or (d[h[p]]<=d[v]) then break;
                h[c]:=h[p];
                pos[h[c]]:=c;
                c:=p;
        until false;
        h[c]:=v;
        pos[v]:=c;
end;

function extract:longint;
var     p,c,v:longint;
begin
        result:=h[1];
        v:=h[nh];
        dec(nh);
        p:=1;
        repeat
                c:=p shl 1;
                if (c<nh) and (d[h[c+1]]<d[h[c]]) then inc(c);
                if (c>nh) or (d[h[c]]>=d[v]) then break;
                h[p]:=h[c];
                pos[h[p]]:=p;
                p:=c;
        until false;
        h[p]:=v;
        pos[v]:=p;
end;

procedure dijkstra;
var     i,u:longint;
begin
        for i:=1 to n do d[i]:=123456789;
        d[1]:=0;
        update(1);
        repeat
                u:=extract;
                if u=n then exit;
                for i:=1 to len[u] do
                begin
                        if d[c[u,i].v]>d[u]+c[u,i].w then
                        begin
                                d[c[u,i].v]:=d[u]+c[u,i].w;
                                update(c[u,i].v);
                        end;
                end;
        until nh=0;
end;

begin
        input;
        dijkstra;
        if d[n]=123456789 then
        write(-1)
        else
        write(trunc(1000*d[n]));
end.

Code mẫu của RR

{$R+,Q+}
const
  FINP='';
  FOUT='';
  MAXN=1000;
  oo=1000000000;
var
  c:array[1..MAXN,1..MAXN] of double;
  d,x,y:array[1..MAXN] of double;
  h,hpos:array[1..MAXN] of longint;
  hsize,n:longint;
  l:double;
function dist(x1,y1,x2,y2:double):double;
begin
  dist:=sqrt(sqr(x1-x2)+sqr(y1-y2));
end;
procedure inp;
var
  f:text;
  i,j,u,v,m:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n,m,l);
  for i:=1 to n do read(f,x[i],y[i]);
  for i:=1 to n do
  for j:=1 to n do
    begin
      c[i,j]:=dist(x[i],y[i],x[j],y[j]);
      if c[i,j]>l then c[i,j]:=oo;
    end;
  for i:=1 to m do
    begin
      read(f,u,v);
      c[u,v]:=0;
      c[v,u]:=0;
    end;
  close(f);
end;
procedure ans;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  if d[n]=oo then writeln(f,-1)
  else writeln(f,trunc(d[n]*1000));
  close(f);
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 shl 1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (d[h[j+1]]<d[h[j]]) then inc(j);
      if (d[h[j]]<d[h[i]]) then
        begin
          swap(hpos[h[i]],hpos[h[j]]);
          swap(h[i],h[j]);
        end;
      i:=j; j:=i shl 1;
    end;
end;
procedure upHeap(i:longint);
var
  j:longint;
begin
  j:=i shr 1;
  while (i>1) and (d[h[i]]<d[h[j]]) do
    begin
      swap(hpos[h[i]],hpos[h[j]]);
      swap(h[i],h[j]);
      i:=j; j:=i shr 1;
    end;
end;
procedure push(u:longint);
begin
  inc(hsize); hpos[u]:=hsize; h[hsize]:=u;
  upHeap(hsize);
end;
procedure pop(var u:longint);
begin
  u:=h[1]; hpos[u]:=0;
  swap(h[1],h[hsize]);
  hpos[h[1]]:=1;
  dec(hsize); downHeap(1);
end;
procedure solve;
var
  u,v:longint;
begin
  for u:=1 to n do d[u]:=oo;
  d[1]:=0; push(1);
  while hsize>0 do
    begin
      pop(u);
      if u=n then exit;
      for v:=1 to n do
      if d[v]>d[u]+c[u,v] then
        begin
          d[v]:=d[u]+c[u,v];
          if hpos[v]=0 then push(v)
          else upHeap(hpos[v]);
        end;
    end;
end;
begin
  inp;
  solve;
  ans;
end.

Code mẫu của hieult

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

using namespace std;

struct diem {  int x,y; };

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

double min(double u,double v)
{
       if(u<v) return u;
       return v;
}

diem A[1010];
double d[1010],m,kq,minn;
int a[1010][1010],n,w,x,y,flag[1010];
long long KQ;

int main()
{
    //freopen("matdien.in","r",stdin);
    scanf("%d %d",&n,&w);
    //printf("%d %d\n",n,w);
    scanf("%lf",&m);
    for(int i = 1;i<=n;i++)
         scanf("%d %d",&A[i].x,&A[i].y);
    for(int i = 1;i<=w;i++)
    {
         scanf("%d %d",&x,&y);
         a[x][y] = 1;
         a[y][x] = 1;
    }
    memset(flag,0,sizeof(flag));
    for(int i = 0;i<1005;i++) d[i] = max;
    int u = 1;
    flag[1] = 1;
    d[1] = 0;
    while(u!=n)
    {
         //printf("***%d*** %lf\n",u,m);      
         int vitri;
         minn = max;
         bool fl = false;
         for(int i = 1;i<=n;i++)
         {

              if(!flag[i])
              {
                   if(a[u][i]==1)
                   {
                        d[i] = d[u];
                   }
                   if(kc(A[u],A[i])<=m+0.0001)
                   {

                        double rich = d[u]+kc(A[u],A[i]);
                        d[i] = min(d[i],rich);
                   }
                   if(d[i]<minn)
                   {
                       // printf("%d %lf.....\n",i,d[i]);
                        vitri = i;
                        minn = d[i];
                        fl = true;
                   }
              }
         }
         u = vitri;
         flag[u]=1;
         if(!fl) break;
    }

    kq = d[n];
    if(kq >= max)
        printf("-1");
    else
    {
    kq = kq*1000;

    //if(kq-(long long)kq<0.5)
        printf("%lld",(long long)kq);
   // else printf("%lld",(long long)kq+1);
    }
    //getch();
}

Code mẫu của ll931110

Program PWRFAIL;
        Const
                input  = '';
                output = '';
                   max = 50000000000000;
               epsilon = 0.000000000001;
        Var
                x,y: array[1..1000] of longint;
                  c: array[1..1000,1..1000] of real;
                  d: array[1..1000] of real;
               free: array[1..1000] of boolean;
                n,w: longint;
                  m: real;
              fi,fo: text;

Procedure init;
          Var
                i: longint;
          Begin
                Assign(fi, input);
                        Reset(fi);

                Readln(fi, n, w);
                Readln(fi, m);

                For i:= 1 to n do readln(fi, x[i], y[i]);
          End;

Procedure LoadGraph;
          Var
                  a,b,k: real;
                i,j,u,v: longint;
          Begin
                For i:= 1 to n do
                  For j:= 1 to n do
                     if i = j then c[i,j]:= 0 else c[i,j]:= max;

                For i:= 1 to n - 1 do
                  For j:= i + 1 to n do
                     Begin
                        a:= x[i] - x[j];        a:= a * a;
                        b:= y[i] - y[j];        b:= b * b;

                        k:= a + b;
                        If k <= m * m then
                                Begin
                                        c[i,j]:= sqrt(k);
                                        c[j,i]:= sqrt(k);
                                End;
                     End;

                For i:= 1 to w do
                        Begin
                                Readln(fi, u, v);
                                c[u,v]:= 0;
                                c[v,u]:= 0;
                        End;
                Close(fi);
          End;

Procedure Dijkstra;
          Var
                u,v,i: longint;
                  min: real;
          Begin
                Fillchar(free, sizeof(free), true);
                For i:= 1 to n do d[i]:= max;
                d[1]:= 0;

                Repeat
                        u:= 0;          min:= max;

                        For i:= 1 to n do
                            if free[i] and (min - d[i] > epsilon) then
                                        Begin
                                                min:= d[i];
                                                u:= i;
                                        End;

                        If (u = 0) or (u = n) then break;
                        free[u]:= false;

                        For v:= 1 to n do
                            if free[v] and (d[v] - d[u] - c[u,v] > epsilon)
                                                     then d[v]:= d[u] + c[u,v];
                Until false;
          End;

Procedure solve;
          Var
                fo: text;
          Begin
                Assign(fo, output);
                        Rewrite(fo);

                If d[n] = max then writeln(fo, -1)
                              else writeln(fo, trunc(d[n] * 1000));
                Close(fo);
          End;

Begin
        init;
        LoadGraph;
        Dijkstra;
        solve;
End.

Code mẫu của skyvn97

#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#define INF   1e11
#define MAX   10101
#define w   first
#define v   second
using namespace std;
typedef pair<double,int> di;
int n;
bool d[MAX][MAX];
vector<di> g[MAX];
int x[MAX];
int y[MAX];
double md[MAX];
void loadgraph(void) {
    double m,t;
    int i,j,k,u,v;
    scanf("%d",&n);
    scanf("%d",&k);
    scanf("%lf",&m);
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&x[i]);
        scanf("%d",&y[i]);
    }
    for (i=1;i<=k;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        d[u][v]=true;
        d[v][u]=true;
    }
    for (i=1;i<n;i=i+1)
        for (j=i+1;j<=n;j=j+1) {
            if (d[i][j]) {
                g[i].push_back(di(0,j));
                g[j].push_back(di(0,i));
            }
            else {
                t=hypot(x[i]-x[j],y[i]-y[j]);
                if (t<=m) {
                    g[i].push_back(di(t,j));
                    g[j].push_back(di(t,i));
                }
            }
        }
    for (i=2;i<=n;i=i+1) md[i]=INF;
    md[1]=0;
}
void dijkstra(void) {
    priority_queue<di,vector<di>,greater<di> > q;
    di x;
    int i,u;
    double d;
    q.push(di(0,1));
    while (!q.empty()) {
        x=q.top();q.pop();
        u=x.v;d=x.w;
        for (i=0;i<g[u].size();i=i+1)
            if (d+g[u][i].w<md[g[u][i].v]) {
                md[g[u][i].v]=d+g[u][i].w;
                q.push(di(md[g[u][i].v],g[u][i].v));
            }
    }
    if (md[n]>=INF) printf("-1");
    else printf("%.0lf",md[n]*1000);
}
int main(void) {
    //freopen("tmp.inp","r",stdin);
    loadgraph();
    dijkstra();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
#include <cmath>
using namespace std;

int n, m;
double maxd;
int x[1010], y[1010];
bool a[1010][1010], inS[1010];
double d[1010];

int main() {
    scanf("%d%d", &n, &m);
    scanf("%lf", &maxd);
    for(int i=0;i<n;++i)
        scanf("%d%d", &x[i], &y[i]);
    for(int i=0;i<m;++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u; --v;
        a[u][v] = a[v][u] = true;
    }
    for(int i=0;i<n;++i) d[i] = 1e11;
    d[0] = 0;
    while(true) {
        int imin = -1;
        double min = 1e11;
        for(int i=0;i<n;++i) if(!inS[i] && d[i] < min) {
            min = d[i];
            imin = i;   
        }   
        if(imin==-1) break;
        inS[imin] = true;
        for(int j=0;j<n;++j) {
            double cost;
            if(a[imin][j]) cost = 0;
            else {
                cost = sqrt((x[imin]-x[j])*1.0*(x[imin]-x[j]) + (y[imin]-y[j])*1.0*(y[imin]-y[j]));
                if(cost - 1e-10 > maxd) cost = 1e11;
            }
            if(d[j] > d[imin] + cost) {
                d[j] = d[imin] + cost;
            }
        }
    }
    if(d[n-1] < 1e10) printf("%d\n", (int)(d[n-1] * 1000 + 1e-10));
    else printf("-1\n");
    // system("pause");
    return 0;
}