[原创]参赛者必进

pk_001

代码长了一点把

knight

我是用十字链表
这样节省空间
不过不是很好写吧
我喜欢有难度的程序设计 ：）

dcyu

图论的问题不一定需要用图的数据结构，用邻接表来描述就足够了，所以用数组就行了，用动态规划的思想在数组中操作就够了。数模竞赛中空间根本不是问题的，256M内存，存一个图的邻接矩阵还怕不够吗。

knight

数学建模的程序都是小程序
但是要为自己封装一些类以背以后用的话，我想还是应该尽量写得好一点
我觉得用空的话要在平时为自己封装一些算法
为以后用（这个程序不是我封装的类，不过我封装了这个算法）

adiehe

我用matlab100行之内就可以搞定！

function [S,D]=minroute(i,m,W)
dd=[];tt=[];ss=[];ss(1,1)=i;V=1:m;V(i)=[];dd=[0;i];
%dd的第二行是每次求出的最短路径的终点，第一行是最短路径的值
kk=2;[mdd,ndd]=size(dd);
while ~isempty(V)
   [tmpd,j]=min(W(i,V));tmpj=V(j);
   for k=2:ndd
      [tmp1,jj]=min(dd(1,k)+W(dd(2,k),V));
      tmp2=V(jj);tt(k-1,=[tmp1,tmp2,jj];
   end
   tmp=[tmpd,tmpj,j;tt];[tmp3,tmp4]=min(tmp(:,1));
   if tmp3==tmpd,ss(1:2,kk)=[i;tmp(tmp4,2)];
   else,tmp5=find(ss(:,tmp4)~=0);tmp6=length(tmp5);
      if dd(2,tmp4)==ss(tmp6,tmp4)
         ss(1:tmp6+1,kk)=[ss(tmp5,tmp4);tmp(tmp4,2)];
      else,ss(1:3,kk)=[i;dd(2,tmp4);tmp(tmp4,2)];
      end
   end
   dd=[dd,[tmp3;tmp(tmp4,2)]];V(tmp(tmp4,3))=[];
   [mdd,ndd]=size(dd);kk=kk+1;
end
S=ss;
D=dd(1,;
   

knight

这个程序本来就很简单
用matlab写就比c++又要少得多
采取的数据结构不一样,程序的长短是不一样的
要用最优化的数据结构

dcyu

http://vip.6to23.com/dcyu/document/arithmetic/Dijkstra.html

飞云0616

好佩服这位的魄力，竟然可以写下这么多的东东！

pk_001

厉害