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=2000;
var a:array[1..maxn,1..maxn] of byte;
    d:array[1..maxn] of longint;
    dau:array[1..maxn] of byte;
    n:integer;
    m:longint;

procedure rf;
var i:longint; x,y:integer;
begin
     fillchar(a,sizeof(a),0);
     readln(n,m);
     for i:=1 to m do
     begin
          readln(x,y);
          a[x,y]:=1; a[y,x]:=1;
     end;
end;

procedure pr;
var i,j,cur,temp:integer;  t,u,min:longint;
begin
     fillchar(dau,sizeof(dau),0);
     for i:=1 to n do d[i]:=maxlongint;
     j:=1; dau[1]:=1; cur:=1; d[1]:=0;
     repeat
           for i:=1 to n do
               if (dau[i]=0) and (a[cur,i]=1) then
               begin
                    if i<cur then
                    begin
                         t:=2*(cur-i);
                         if d[cur] mod t = cur-i then u:=cur-i
                         else u:=cur-i+d[cur] mod t;
                    end
                    else
                    begin
                         t:=2*(i-cur);
                         if d[cur] mod t = 0 then u:=i-cur
                         else u:=i-cur+t-d[cur] mod t;
                    end;
                    if d[cur]+u<d[i] then d[i]:=d[cur]+u;
               end;
           min:=maxlongint;
           for i:=1 to n do
               if (dau[i]=0) and (d[i]<min) then
               begin
                    min:=d[i];
                    temp:=i;
               end;
           cur:=temp; dau[cur]:=1;
     until (dau[n]=1) or (j=n);
end;

procedure wf;
begin
     write(d[n]*5);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#include <climits>
#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 FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 1010;
using namespace std;
int d[N];
int n, m;
VI a[N];

void dijkstra() {
    priority_queue<II, vector<II>, greater<II> > Q;
    Q.push(MP(0, 1));
    REP(i, 2, n) d[i] = INT_MAX;
    while (!Q.empty()) {
        int u = Q.top().Y, du = Q.top().X; Q.pop();
        if (du != d[u]) continue;
        if (u == n) break;
        int duu;
        FOR(i, 0, SZ(a[u])) {
            int v = a[u][i];
            int dist = abs(u - v);
            if (u < v) {
                if (du % dist == 0) duu = ((du / dist) & 1) ? du + dist : du;
                else {
                    if ((du / dist) & 1) duu = du / dist * dist + dist;
                    else duu = du / dist * dist + dist + dist;
                }
            }
            else {
                if (du % dist == 0) duu = ((du / dist) & 1) ? du : du + dist;
                else {
                    if ((du / dist) & 1) duu = du / dist * dist + dist + dist;
                    else duu = du / dist * dist + dist;
                }
            }
            if (d[v] > duu + dist) {
                d[v] = duu + dist;
                Q.push(MP(d[v], v));
            }
        }
    }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int u, v;
    FOR(i, 0, m) {
        cin >> u >> v;
        a[u].PB(v); a[v].PB(u);
    }
    dijkstra();
    cout << d[n] * 5;
    return 0;
}

Code mẫu của RR

//Written by RR
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>

#define MAXN 1111
#define FOR(i,a,b) for(long i=a; i<=b; i++)
#define V vector<long>
#define FORV(i,v) for(V::iterator i=v.begin(); i!=v.end(); i++)
#define PB push_back
#define MP make_pair

using namespace std;
typedef pair< long, long > ii;

long n,k,dist[MAXN];
V ke[MAXN];
priority_queue <ii,vector<ii>,greater<ii> > pq;

void inp() {
     scanf("%ld %ld",&k,&n);
     FOR(i,1,n) {
                long u,v;
                scanf("%ld %ld",&u,&v);
                ke[u].PB(v);
                ke[v].PB(u);
     }
}

void solve() {
     FOR(i,2,k) dist[i]=1000111000;
     pq.push(MP(0,1));
     while (!pq.empty()) {
           ii top=pq.top(); pq.pop();
           long v=top.second,d=top.first;
           if (d<=dist[v])
           FORV(u,ke[v])
             if (*u>v) {
                       long len=*u-v;
                       long temp=(dist[v]/(len<<1))*len<<1; if (temp<dist[v]) temp+=len<<1;
                       temp+=len;
//                       printf("%ld -> %ld %ld\n",v,*u,temp);
                       if (temp<dist[*u]) {dist[*u]=temp; pq.push(MP(dist[*u],*u)); }
             } else {
                    long len=v-*u;
                    long temp=((dist[v]-len)/(len<<1))*(len<<1)+len; 
                    if (temp<dist[v]) temp+=len<<1;
                    temp+=len;
//                    printf("%ld -> %ld %ld\n",v,*u,temp);
                    if (temp<dist[*u]) {dist[*u]=temp; pq.push(MP(dist[*u],*u)); }
             }
     }
     printf("%lld\n",5LL*dist[k]);
}

int main() {
    #ifdef DEBUG
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);
    #endif
    inp();
    solve();
    return 0;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) {
    stringstream ss;
    if (p >= 0)
        ss << fixed << setprecision(p);
    ss << a;
    T r;
    ss >> r;
    return r;
}
template<class T> T gcd(T a, T b) {
    T r;
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
template<class T> T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}
template<class T> T sqr(T x) {
    return x * x;
}
template<class T> T cube(T x) {
    return x * x * x;
}
template<class T> int getbit(T s, int i) {
    return (s >> i) & 1;
}
template<class T> T onbit(T s, int i) {
    return s | (T(1) << i);
}
template<class T> T offbit(T s, int i) {
    return s & (~(T(1) << i));
}
template<class T> int cntbit(T s) {
    return s == 0 ? 0 : cntbit(s >> 1) + (s & 1);
}

const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
    if (rsz <= 0) {
        ptr = 0;
        rsz = (int) fread(bf, 1, bfsz, stdin);
        if (rsz <= 0)
            return EOF;
    }
    --rsz;
    return bf[ptr++];
}
void ga(char &c) {
    c = EOF;
    while (!isalpha(c))
        c = gc();
}
int gs(char s[]) {
    int l = 0;
    char c = gc();
    while (isspace(c))
        c = gc();
    while (c != EOF && !isspace(c)) {
        s[l++] = c;
        c = gc();
    }
    s[l] = '\0';
    return l;
}
template<class T> bool gi(T &v) {
    v = 0;
    char c = gc();
    while (c != EOF && c != '-' && !isdigit(c))
        c = gc();
    if (c == EOF)
        return false;
    bool neg = c == '-';
    if (neg)
        c = gc();
    while (isdigit(c)) {
        v = v * 10 + c - '0';
        c = gc();
    }
    if (neg)
        v = -v;
    return true;
}

typedef pair<int, int> II;
const ld PI = acos(-1.0);
const ld eps = 1e-12;
const int dr[] = { -1, 0, +1, 0};
const int dc[] = { 0, +1, 0, -1};
const int inf = (int) 1e9 + 5;
const ll linf = (ll) 1e18 + 5;
const int mod = (ll) (1e9 + eps);

using namespace std;

#define maxn 1005
#define maxe 200005

int last[maxn], adj[maxe], next[maxe], f[maxn], E = 0;
int n, m;

void add(int u, int v){
    adj[E] = v; next[E] = last[u]; last[u] = E++;
    adj[E] = u; next[E] = last[v]; last[v] = E++;
}

int main(){
//  freopen("in.txt", "r", stdin);

    cin >> n >> m;
    int u, v, c, T;
    ms(last, -1); E = 0;
    Rep(run, m){
        scanf("%d %d", &u, &v);
        add(u, v);
    }
    priority_queue<II> que;
    ms(f, 0x3f); f[1] = 0;
    que.push(mp(0, 1));
    while(!que.empty()){
        c = -que.top().fi; u = que.top().se; que.pop();
        if(f[u] < c) continue;
        if(u == n) break;
        for(int e = last[u]; e != -1; e = next[e]){
            v = adj[e];
            if(u < v) T = ((c + (v + v - u - u - 1)) / (v + v - u - u)) * (v + v - u - u) + v - u;
            else T = ((c + (u - v - 1)) / (u + u - v - v)) * (u + u - v - v) + u + u - v - v;
            if(T < f[v]){
                f[v] = T;
                que.push(mp(-f[v], v));
            }
        }
    }

    cout << f[n] * 5;

    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> ke[50050];
int n, m;
int F[50050];

int main() {
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;++i) {
        int u, v;
        scanf("%d%d", &u, &v);  
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    queue<int> q;
    memset( F, 0x1f, sizeof(F));
    F[1] = 0;
    q.push(1);
    while(!q.empty()) {
        int u = q.front();
        int t = F[u];
        q.pop();
        for(int k=0;k<ke[u].size();++k) {
            int v = ke[u][k];
            int len = u - v;
            if(len < 0) len = -len;
            if(u < v) {
                int z = t;
                if(z % (2*len) != 0) 
                    z = (z / (2*len) + 1) * 2 * len;
                if(F[v] > z + len) {
                    F[v] = z + len;
                    q.push(v);  
                }
            }
            else {
                int z = t;
                if(z % (2*len) != len) {
                    if(z % (2*len) < len) {
                        z = z / (2*len) * (2*len) + len;    
                    }
                    else {
                        z = (z / (2*len) + 1) * (2*len) + len;  
                    }
                }   
                if(F[v] > z + len) {
                    F[v] = z + len;
                    q.push(v);  
                }
            }
        }   
    }
    cout << F[n] * 5 << endl;
    // system("pause");
    return 0;   
}