此题我用的算法是Dijkstra（我这是第2次用此算法）
这题有如下注意点
1.起点是1，终点是n
2.这是一张有向图（我为此wa了一次，悲剧）
3.注意要开一个数组专门记录在最优路径下，某个点的前一个点是什么
附上代码（比较丑陋，希望不要介意）

var
map:array[1..1000,1..1000]of longint;
d,qq,visit,a:array[1..1000]of longint;
i,j,n,k,min,head,x:longint;
begin
read(n);
fillchar(map,sizeof(map),0);
for i:=1 to n do
for j:=1 to n do
begin
read(x);
if x<>0
then
begin
map[i,j]:=x
end;
end;
for i:=1 to n do d[i]:=maxlongint;
k:=1;
qq[1]:=1;
d[1]:=0;
fillchar(visit,sizeof(visit),0);
visit[1]:=1;
for i:=1 to n do
begin
visit[k]:=1;
for j:=1 to n do
begin
if map[k,j]<>0
then
begin
if d[j]>d[k]+map[k,j]
then
begin
qq[j]:=k;
d[j]:=d[k]+map[k,j];
end;
end;
end;
min:=maxlongint;
for j:=1 to n do
begin
if (visit[j]=0)and(d[j]<min)
then
begin
min:=d[j];
k:=j;
end;
end;
end;
i:=n;
head:=1;
while i>1 do
begin
a[head]:=i;
i:=qq[i];
inc(head);
end;
write(1,' ');
for i:=head-1 downto 2 do write(a[i],' ');
writeln(a[1]);
writeln(d[n]);
end.