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

#include<iostream>
#define oo 1000000000
#define fr(a,b,c) for (a=b;a<=c;a++)
#define frr(a,b,c) for (a=b;a>=c;a++)
using namespace std;
int n,m,g,h,q,i,j,x,y,a[33][33],d[33][33],kt,dx[4],dy[4],b[999],c[999],t[999];
int main()
{
   dx[0]=0; dx[1]=1; dx[2]=0; dx[3]=-1;
   dy[0]=1; dy[1]=0; dy[2]=-1; dy[3]=0;
   while (1)
   {
         cin >> m >> n;
         if (!m && !n) break;
         fr(x,0,m-1)
          fr(y,0,n-1)
          {
             a[x][y]=0; d[x][y]=oo;
          }
         cin >> g;
         while (g--)
         {
               scanf("%d%d",&x,&y);
               a[x][y]=-1;
         }
         cin >> h;
         fr(i,1,h)
         {
            scanf("%d%d%d%d%d",&x,&y,&b[i],&c[i],&t[i]);
            a[x][y]=i;
         }
         d[0][0]=0; 
         fr(i,1,n*m)
         {
             kt=1;
             fr(x,0,m-1)
               fr(y,0,n-1)
                if (d[x][y]<oo)
                 if (a[x][y]>0)
                 {
                    g=a[x][y];
                    if (d[b[g]][c[g]]>d[x][y]+t[g])
                    {
                       d[b[g]][c[g]]=d[x][y]+t[g]; 
                       kt=0;
                    }
                 }
                 else
                 {
                     if (a[x][y]<0 || (x==m-1 && y==n-1)) continue;
                     fr(g,0,3)
                     {
                        int u=x+dx[g],v=y+dy[g]; 
                        if (u>=0 && v>=0 && u<m && v<n && a[u][v]>=0 && d[u][v]>d[x][y]+1)
                        {
                           d[u][v]=d[x][y]+1;
                           kt=0;
                        }
                     }
                 }
             if (kt) break;
         } 
         if (!kt) cout << "Never";
         else
         {
             if (d[m-1][n-1]==oo) cout << "Impossible";
             else cout << d[m-1][n-1];
         }
         cout << endl;
   }
   return 0;
}

Code mẫu của RR

#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);

typedef pair<int,int> P;
typedef pair< P, int> PP;

int m, n, a[55][55], nEdge, d[100111];
PP e[100111];

int encode(int u, int v) {
    return (u-1) * n + v;
}

void add(int u, int v, int c) {
    e[nEdge].F.F = u;
    e[nEdge].F.S = v;
    e[nEdge].S = c;
    nEdge++;
}

const int di[4] = {-1,1,0,0};
const int dj[4] = {0,0,-1,1};
const int oo = 1000111000;

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    while (true) {
        nEdge = 0;

        scanf("%d %d", &n, &m);
        if (m == 0) break;
        memset(a, 0, sizeof a);
        int g; scanf("%d", &g);
        while (g--) {
            int u, v; scanf("%d %d", &v, &u);
            u++; v++;
            a[u][v] = 1;
        }

        scanf("%d", &g);
        while (g--) {
            int u, v, x, y, c;
            scanf("%d %d %d %d %d", &v, &u, &y, &x, &c);
            u++; v++; x++; y++;
            a[u][v] = 2;
            add(encode(u,v), encode(x, y), c);
        }

        FOR(i,1,m) FOR(j,1,n)
        if (a[i][j] == 0) 
        REP(dir,4) {
            int ii = i + di[dir], jj = j + dj[dir];
            if (ii > 0 && ii <= m && jj > 0 && jj <= n)
                if (a[ii][jj] != 1) add(encode(i,j), encode(ii,jj), 1);
        }

        int update;
        FOR(i,1,m*n) d[i] = oo;
        if (a[1][1] != 1) d[encode(1,1)] = 0;
        REP(turn,m*n+2) {
            update = 0;
            REP(x,nEdge) {
                int u = e[x].F.F, v = e[x].F.S, c = e[x].S;
                if (u != encode(m,n) && d[u] != oo && d[u] + c < d[v]) {
                    d[v] = d[u] + c;
                    update = 1;
                }
            }
        }
        if (update) puts("Never");
        else if (d[encode(m,n)] >= oo) puts("Impossible");
        else printf("%d\n", d[encode(m,n)]);
    }
    return 0;
}