Program sksks; Var n,s,i,j:longint; f:array[1..1024,1..1024] of longint; Procedure Dijkstra(s,n:longint); Var i,j,min,p:longint; vis:array[1..1024] of boolean; d:array[1..1024] of longint; Begin fillchar(vis,sizeof(vis),0); for i:=1 to n do if f[s,i]=0 then d[i]:=MaxLongInt div 10 else d[i]:=f[s,i]; d[s]:=0; vis[s]:=true; for i:=1 to n-1 do begin min:=MaxLongInt div 10; for j:=1 to n do if (NOT vis[j]) AND (min>d[j]) then begin p:=j; min:=d[j]; end; vis[p]:=true; writeln('p:',p); for j:=1 to n do if (NOT vis[j]) then if d[p]+f[p,j]<d[j] then d[j]:=d[p]+f[p,j]; end; for i:=1 to n do if s<>i then writeln(s,'---->',i,':',d[i]); End; Begin readln(n,s); for i:=1 to n do for j:=1 to n do read(f[i,j]); Dijkstra(s,n); End.
{ Prim算法和Kruskal算法和并查集思想的结合之最小生成树算法 打字By:SpringHack 边集数组表示法 } Program sksks; Var a,b,c:array[1..1024] of longint; i,n,p:longint; procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=c[(l+r) div 2]; repeat while c[i]<x do inc(i); while x<c[j] do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; y:=b[i]; b[i]:=b[j]; b[j]:=y; y:=c[i]; c[i]:=c[j]; c[j]:=y; inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; Procedure Prim(n,p:longint); Var i,j:longint; v:array[1..1024] of integer; d:array[1..1024] of boolean; Begin sort(1,p); fillchar(v,sizeof(v),0); fillchar(d,sizeof(d),0); v[1]:=1; for i:=2 to n do begin j:=1; while NOT ((v[a[j]]<>v[b[j]]) AND (NOT d[j])) do inc(j); v[a[j]]:=1; v[b[j]]:=1; d[j]:=true; end; for i:=1 to p do if d[i] then writeln(a[i],'---->',b[i],':',c[i]); End; Begin readln(n,p); for i:=1 to p do readln(a[i],b[i],c[i]); Prim(n,p); End.