为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

新建文件夹2

2010-11-09 35页 doc 3KB 531阅读

用户头像

is_161215

暂无简介

举报
新建文件夹2 新建文件夹2/djis.pas {复杂度O(n^2),求一个点到其他点的最短路径,不可处理有非正权的情况} const big:longint=1000000000;//一个很大的数 var x,y,z,i,j,k,t,n,m,min:longint; a:array[1..100,1..100]of longint; d:array[1..100]of longint; flag:array[1..100]of boolean;//记录点是否已找到到源点的最短路径 begin;...
新建文件夹2
新建文件夹2/djis.pas {复杂度O(n^2),求一个点到其他点的最短路径,不可处理有非正权的情况} const big:longint=1000000000;//一个很大的数 var x,y,z,i,j,k,t,n,m,min:longint; a:array[1..100,1..100]of longint; d:array[1..100]of longint; flag:array[1..100]of boolean;//记录点是否已找到到源点的最短路径 begin; fillchar(flag,sizeof(flag),false); readln(n); for x:=1 to n do for y:=1 to n do read(a[x,y]); for x:=1 to n do if a[1,x]=0 then d[x]:=big else d[x]:=a[1,x]; for x:=1 to n do d[x]:=a[1,x]; flag[1]:=true; for x:=2 to n do begin; min:=big; for y:=1 to n do if (flag[y]=false) and (d[y]0) and (a[t,y]+d[t]0) and (d[y]=0) then d[y]:=a[t,y]+d[t]; end; end; writeln(d[n]); end. 新建文件夹2/floyd.pasconst big=1000000000; var x,y,z,i,j,k,n:longint; map:array[1..100,1..100]of longint; procedure init; begin; readln(n); for x:=1 to n do for y:=1 to n do begin; read(map[x,y]); if map[x,y]=0 then map[x,y]:=big;//x与y不联通 end; end; procedure floyed; begin; for k:=1 to n do//中间点 for i:=1 to n do//一个点 for j:=1 to n do//另一个点 if ((k<>i)and(i<>j)and(k<>j)and(map[i,j]>map[i,k]+map[k,j])) then map[i,j]:=map[i,k]+map[k,j];//这三点没有重合,且经过中间点可以使路径变短,则更改 end; begin; init; floyed; writeln(map[1,n]);//也可以输出其他点到任意点的最短路径 end. 新建文件夹2/spfa.pasconst big:longint=1000000000; var head,tail,x,y,m,nt,t1,t2,t3:longint; a:array[1..801,0..801,1..2]of longint; p:array[1..801]of boolean; dl,d:array[1..801]of longint; begin; readln(n,m); for x:=1 to m do begin; readln(t1,t2,t3); inc(a[t1,0,1]); a[t1,a[t1,0,1],1]:=t2; a[t1,a[t1,0,1],2]:=t3; inc(a[t2,0,1]); a[t2,a[t2,0,1],1]:=t1; a[t2,a[t2,0,1],2]:=t3; end; for y:=1 to n do d[y]:=big; head:=0; tail:=1; dl[1]:=1; d[1]:=0; p[1]:=true; while head<>tail do begin; head:=(head mod n)+1; t:=dl[head]; p[t]:=false; for y:=1 to a[t,0,1] do if d[a[t,y,1]]>a[t,y,2]+d[t] then begin; d[a[t,y,1]]:=a[t,y,2]+d[t]; if p[a[t,y,1]]=false then begin; p[a[t,y,1]]:=true; tail:=(tail mod n)+1; dl[tail]:=a[t,y,1]; end; end; end. 新建文件夹2/crsk.pasvar x,y,z,n,m,k1,k2,e1,e2:longint; a:array[1..15000,1..3]of longint; f:array[1..1000]of longint; procedure qsort(l,r:longint); var tmp,i,j,mid:longint; begin; i:=l; j:=r; mid:=a[(i+j)div 2,3]; repeat while a[i,3]mid do dec(j); if i<=j then begin tmp:=a[i,3];a[i,3]:=a[j,3];a[j,3]:=tmp; tmp:=a[i,2];a[i,2]:=a[j,2];a[j,2]:=tmp; tmp:=a[i,1];a[i,1]:=a[j,1];a[j,1]:=tmp; inc(i); dec(j); end; until i>j; if lk2 then begin; inc(e2); f[k1]:=k2; end; until e2=n-1; writeln(a[e1,3]); end. 新建文件夹2/a.txt const big:longint=1000000000;//一个很大的数 var x,y,z,i,j,k,t,n,m,min:longint; map:array[1..100,1..100]of longint; d:array[1..100]of longint; flag:array[1..100]of boolean;//记录点是否已找到到源点的最短路径 begin; fillchar(flag,sizeof(flag),false); readln(n); for x:=1 to n do for y:=1 to n do read(map[x,y]); for x:=1 to n do d[x]:=map[1,x]; flag[1]:=true; for x:=2 to n do begin; min:=big; for y:=1 to n do if ((flag[y]=false) and (d[y]0)) then begin;min:=d[y];t:=y;end;//找到当前到源点最短的点 flag[t]:=true;//此时该点已经找到到源点的最短距离 for y:=1 to n do//用该点去更新其他没有找到最短路径的点 begin; if ((flag[y]=false) and (map[t,y]<>0) and(map[t,y]+d[t]0) and (d[y]=0)) then d[y]:=map[t,y]+d[t]; end; end; writeln(d[n]); end. 新建文件夹2/b.txt var min,t,x,y,z,i,j,k,m,n,total:longint; d:array[1..100]of longint;//点到生成树的最短距离 map:array[1..100,1..100]of longint; f:array[1..100]of boolean;//已经在生成树里的纪录为true begin; readln(n); for x:=1 to n do for y:=1 to n do begin; read(map[x,y]); if map[x,y]=0 then map[x,y]:=1000000000;//x与y不联通 end; for x:=1 to n do d[x]:=map[1,x]; fillchar(f,sizeof(f),false); f[1]:=true; for x:=1 to n-1 do begin; min:=1000000000; for y:=1 to n do if ((f[y]=false) and (d[y]map[t,y])) then begin;d[y]:=map[t,y];end;//更新那些不在生成树的点到生成树的最短距离 end; writeln(total); end.
/
本文档为【新建文件夹2】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索