新建文件夹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.