我把自己写的代码贴出来你参考一下吧，
思想是djstra的思想，好象这个思想的本质也是动态规划
#include <stdio.h>
FILE *fi;
int data[50][50],len[50][50],dest[2],n;
void in(int n)
{int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
fscanf(fi,"%d",&data[i][j]);}
int change(int a,int b,int da)
{int t;
/*change函数用于更新标记len[a][b]
da为和它相邻的一个刚确定最短路径
的结点的最短路径值，
更新目标是更新目前已经知道的最短路径长*/
if(a<0||b<0||a>=n||b>=n)return 0;
t=da-data[a][b];
if(len[a][b]==0)
{len[a][b]=t;
return 0;}
if(len[a][b]<t)len[a][b]=t;
return 0; }
int find()
{int i,j,min,mi1,mi2;
min=-30000;
/*这是算法的核心函数，它找出目前已经知道的所有
最短路径长中最短的，它必然是起点到该点的最短路径长*/
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{if(len[i][j]>=0)continue;
if(len[i][j]>min)
{mi1=i;mi2=j;
min=len[i][j];}}
/*每次只要更新4个目标，思考一下为什么*/
change(mi1+1,mi2,len[mi1][mi2]);
change(mi1-1,mi2,len[mi1][mi2]);
change(mi1,mi2+1,len[mi1][mi2]);
change(mi1,mi2-1,len[mi1][mi2]);
len[mi1][mi2]=-len[mi1][mi2];
if(mi1==dest[0]&&mi2==dest[1])
return 1;
else return 0;
/*如果得到右上角的最短路径，返回1*/}
void djstra()
{int i,j;
for(i=0;i<n;i++)
for(j=0;j<0;j++)
len[i][j]=0;
dest[0]=0;
dest[1]=n-1;
len[n-1][0]=data[n-1][0];
len[n-2][0]=-data[n-1][0]-data[n-2][0];
len[n-1][1]=-data[n-1][0]-data[n-1][1];
/*上面为一些必要的初始化,dest储存最终目标（右上角），
len里面储存：当元素>0时:起点到该点的最短路径长；
当元素<0时：目前已经知道的最短路径长（但不一定时最短路径）
=0；未被标记*/
while(!find());}
int main()
{char fn[10];
scanf("%d",&n);/*在这里输入，N(N<=50)即正方形的边长*/
scanf("%s",fn);/*在这里输入输入文件名*/
fi=fopen(fn,"r");
in(n);
djstra();
printf("%d\n",len[0][n-1]);
getch();
fclose(fi);
return 0;}
[此贴子已经被作者于2004-12-28 20:03:02编辑过]
