uva10986 堆优化单源最短路径(pas)
2024-10-19 04:26:10
var n,m,s,t,v,i,a,b,c:longint;//这道题的代码不是这个，在下面
first,tr,p,q:array[..]of longint;
next,eb,ew:array[..]of longint;
procedure swap(a,b:longint);
var t:longint;
begin
t:=tr[a];tr[a]:=tr[b];tr[b]:=t;
t:=p[a];p[a]:=p[b];p[b]:=t;
t:=q[p[a]];q[p[a]]:=q[p[b]];q[p[b]]:=t;
end;
procedure sw(var a,b:longint);
var t:longint;
begin
t:=a;a:=b;b:=t;
end;
procedure up(a:longint);
begin
if a= then exit;
if tr[a]<tr[a div ] then
begin
swap(a,a div );
up(a div );
end;
end;
procedure down(a:longint);
var b,c:longint;
begin
b:=;
while(b<=a div )do
begin
c:=b*;
if(tr[c]>tr[c+])and(c<n)then
c:=c+;
if tr[c]<tr[b] then
swap(b,c);
b:=c;
end;
end;
procedure input;
begin
v:=v+;
eb[v]:=b;
ew[v]:=c;
next[v]:=first[a];
first[a]:=v;
end;
begin
readln(n,m,s,t);
v:=;
fillchar(first,sizeof(first),);
for i:= to m do
begin
readln(a,b,c);
input;
sw(a,b);
input;
end;
fillchar(tr,sizeof(tr),$7f);
tr[s+]:=;
for i:= to n do
begin
p[i]:=i-;
q[i-]:=i;
end;
up(s+);
write('Case #1: ');
repeat
a:=p[]; //top
if a=t then
begin
if tr[]= then
writeln('unreachable')
else
writeln(tr[]);
break;
end;
b:=first[a];
while(b<>)do
begin
c:=eb[b];
if(tr[q[a]]+ew[b]<tr[q[c]])then
begin
tr[q[c]]:=tr[q[a]]+ew[b];
up(q[c]);
end;
b:=next[b];
end;
swap(,n);
n:=n-;
down(n);
until false;
end.
单纯的堆优化dijkstra，
加上多组数据以后（该题AC)：
var n,m,s,t,v,i,a,b,c,nn,ii:longint;
first,tr,p,q:array[..]of longint;
next,eb,ew:array[..]of longint;
procedure swap(a,b:longint);
var t:longint;
begin
t:=tr[a];tr[a]:=tr[b];tr[b]:=t;
t:=p[a];p[a]:=p[b];p[b]:=t;
t:=q[p[a]];q[p[a]]:=q[p[b]];q[p[b]]:=t;
end;
procedure sw(var a,b:longint);
var t:longint;
begin
t:=a;a:=b;b:=t;
end;
procedure up(a:longint);
begin
if a= then exit;
if tr[a]<tr[a div ] then
begin
swap(a,a div );
up(a div );
end;
end;
procedure down(a:longint);
var b,c:longint;
begin
b:=;
while(b<=a div )do
begin
c:=b*;
if(tr[c]>tr[c+])and(c<n)then
c:=c+;
if tr[c]<tr[b] then
swap(b,c);
b:=c;
end;
end;
procedure input;
begin
v:=v+;
eb[v]:=b;
ew[v]:=c;
next[v]:=first[a];
first[a]:=v;
end;
begin
readln(nn);
for ii:= to nn do
begin
readln(n,m,s,t);
v:=;
fillchar(first,sizeof(first),);
for i:= to m do
begin
readln(a,b,c);
input;
sw(a,b);
input;
end;
fillchar(tr,sizeof(tr),$7f);
tr[s+]:=;
for i:= to n do
begin
p[i]:=i-;
q[i-]:=i;
end;
up(s+);
write('Case #',ii,': ');
repeat
a:=p[]; //top
if a=t then
begin
if tr[]= then
writeln('unreachable')
else
writeln(tr[]);
break;
end;
b:=first[a];
while(b<>)do
begin
c:=eb[b];
if(tr[q[a]]+ew[b]<tr[q[c]])then
begin
tr[q[c]]:=tr[q[a]]+ew[b];
up(q[c]);
end;
b:=next[b];
end;
swap(,n);
n:=n-;
down(n);
until false;
end;
end.
最新文章
- 使用D3绘制图表（3）--添加坐标轴和文本标签
- JavaScript笔记杂谈篇(啥都有)
- init/main.c
- editplus如何设置不自动备份
- Spring中Bean的命名问题及ref和idref之间的区别
- javaDay1 基础知识
- Oracle EBS-SQL (PO-5):采购订单控制信息查询.sql
- 通过终端使用ssh-keygen免密码登录远程服务器
- 多租户实现之基于Mybatis,Mycat的共享数据库，共享数据架构
- boost asio 学习(四)使用strand将任务排序
- Implement strStr() leetcode java
- UVA 11796 Dog Distance(几何)
- SpringBoot简单的REST风格例子
- 用Hadoop AVRO进行大量小文件的处理（转）
- 基于FPGA的I2C读写EEPROM
- 微信 JS-SDK 签名验证
- Shiro安全框架学习笔记
- Android中的Audio播放：竞争Audio之Audio Focus的应用
- linux后退文件夹命令
- linux 程序启动与停止管理脚本