MÊ CUNG

 MÊ CUNG

#include<stdio.h>
#define MAX_VERTICES 100
#define NO_EDGE 0
#define INFINITY 99999

int w[MAX_VERTICES];
int u[MAX_VERTICES];
int mark[MAX_VERTICES], pi[MAX_VERTICES],p[MAX_VERTICES];
typedef struct{
    int n;
    int A[MAX_VERTICES][MAX_VERTICES];
}Graph;

void init_graph(Graph* G, int n){
    int i,j;
    G->n=n;
    for (i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            G->A[i][j]=NO_EDGE;        
}
void add_edge(Graph* G, int u,int v,int w){
    G->A[u][v]=w;
}
void Dijkstra(Graph* G,int s){
    int i,j,it;
    for(i=1;i<=G->n;i++){
        pi[i]=INFINITY;
        mark[i]=0;
    }
    pi[s]=w[s];
    p[s]=-1;
    
    for(it=1; it<G->n; it++){
        int min_pi=INFINITY;
        for(j=1; j<=G->n; j++)
            if(mark[j]==0 && pi[j]<min_pi){
                min_pi=pi[j];
                i=j;
            }
        mark[i]=1;
        for(j=1; j<=G->n; j++)
            if(G->A[i][j]!=NO_EDGE && mark[j]==0){
                if(pi[i]+G->A[i][j]<pi[j]){
                    pi[j]=pi[i]+G->A[i][j];
                    p[j]=i;
                }
            }
    }
}
int main (){
    Graph G;
    int i,j,m,n,u,e,k;
    //freopen("mecung.txt", "r", stdin);    
    scanf("%d%d", &m, &n);
    
    for(i=0;i<m;i++)
        for(j=0;j<n;j++){
            u=(i*n+j)+1;
            scanf("%d",&e);
            w[u]=e;
        }
    init_graph(&G,n*m);
    int di[]={-1,1,0,0};
    int dj[]={0,0,-1,1};
    
    for(i=0;i<m;i++)
        for(j=0;j<n;j++){
            u=(i*n+j)+1;
            for(k=0;k<4;k++){
                int ii=i+di[k];
                int jj=j+dj[k];
                if(ii>=0 && ii<n && jj>=0 && jj<m){
                    int v=(ii*n+jj)+1;
                    add_edge(&G ,v,u,w[u]);
                }
        }
    }
    Dijkstra(&G,1);
    printf("%d",pi[G.n]);
    return 0;
}