COGS 497——奶牛派对
2024-08-31 00:54:52
我们发现每头牛需要走的路程即为它到x的最短路+x到它的最短路。
转化：
于是这道题变成了一道典型的单源最短路问题，只需求出每个点到x的最短路dl，以及从x到此点的最短路d2，然后去找max(dl+d2)即可。
效率分析：
使用dijsktra算法，时间复杂度为O(n^2)。
【我的程序】
type aa=array[..,..] of longint;
var
n,m,x,a,b,t,i,j,k,min,max:longint;
map1,map2:aa;
ans:array[..] of longint;
f:array[..] of boolean;
d:array[..] of longint;
procedure dijkstra(map:aa);
begin
for i:= to n do
begin d[i]:=map[x,i]; f[i]:=false; end;
f[x]:=true;
for i:= to n do
begin
min:=maxlongint; k:=;
for j:= to n do
if (not f[j]) and (d[j]<min) then
begin min:=d[j]; k:=j; end;
if (k=) or (min=maxlongint) then exit;
f[k]:=true;
for j:= to n do
if (not f[j]) and (d[k]+map[k,j]<d[j])
then d[j]:=d[k]+map[k,j];
end;
for i:= to n do ans[i]:=ans[i]+d[i];
end;
begin
assign(input,'party.in');
reset(input);
assign(output,'party.out');
rewrite(output);
readln(n,m,x);
for i:= to n do
for j:= to n do
if i=j then begin map1[i,j]:=; map2[i,j]:=; end
else begin map1[i,j]:=maxlongint div ; map2[i,j]:=maxlongint div ; end;
for i:= to m do
begin
readln(a,b,t);
map1[a,b]:=t;
map2[b,a]:=t;//if (map[a,b]>t) or (map[a,b]=) then map[a,b]:=t;
end;
dijkstra(map1);
dijkstra(map2);
for i:= to n do if ans[i]>max then max:=ans[i];
writeln(max);
end.
【老师给的标程】
const
maxn=;
maxm=;
var
n,m,X,i,j,sum,ans:longint;
path:array[..,..maxn,..maxn]of Longint;
dis:array[..,..maxn]of Longint;
v:array[..maxn]of boolean;
procedure Init;
var
A,b,c:Longint;
begin
readln(n,m,X);
for i := to n do
for j:= to n do
begin
path[,i,j]:=maxm;
path[,i,j]:=maxm;
end;
for i := to m do
begin
readln(A,b,c);
If path[,A,b] > c then
begin
path[,A,b] := c;
path[,b,A] := c;
end;
end;
end;
procedure dij(k:longint);
var
min,minj,i,j,t:Longint;
begin
fillchar(v,sizeof(v),false);
for i := To n do
If path[k,X,i] <> maxm then dis[k,i] := path[k,X,i]
else dis[k,i] := maxm;
v[x] := true;
dis[k,x] := ;
for i := n- downto do
begin
min:=maxm;
for j := to n do
if (dis[k,j] < min)And(not v[j]) then
begin
min := dis[k,j];
minj := j;
end;
if min<>maxm then
begin
v[minj] := true;
j:=minj;
for t := to n do
If (dis[k,j]+path[k,j,t] < dis[k,t])And(not v[t]) Then
dis[k,t] := dis[k,j]+path[k,j,t];
end;
end;
end;
procedure main;
begin
dij();
dij();
Ans:=;
for i := to n do
begin
sum := dis[,i]+dis[,i];
If (sum>ans)and(i<>X) then ans:=sum;
end;
end;
procedure Ouit;
begin
Writeln(ans);
end;
begin
Init;
main;
Ouit;
end.
【考试时错误的做法】还是没有真正理解dijkstra
var
i,j,n,m,x,k1,k2,w,min,k,max:longint;
a:array[..,..] of longint;
d,ans:array[..] of longint;
f:array[..] of boolean;
procedure dijkstra1;
begin
for i:= to n do
begin d[i]:=a[x,i]; f[i]:=false; end;
f[x]:=true;
for i:= to n do
begin
min:=maxlongint; k:=;
for j:= to n do
if (not f[j]) and (d[j]<min) then
begin
min:=d[j]; k:=j;
end;
if (k=)or(min=maxint) then exit;
f[k]:=true;
for j:= to n do
if (not f[j]) and (d[k]+a[k,j]<d[j]) then d[j]:=d[k]+a[k,j];
end;
end;
procedure dijkstra2;
begin
for i:= to n do
begin d[i]:=a[i,x]; f[i]:=false; end;
f[x]:=true;
for i:= to n do
begin
min:=maxlongint; k:=;
for j:= to n do
if (not f[j]) and (d[j]<min) then
begin
min:=d[j]; k:=j;
end;
if (k=)or(min=maxint) then exit;
f[k]:=true;
for j:= to n do
if (not f[j]) and (d[k]+a[k,j]<d[j]) then d[j]:=d[k]+a[k,j];
end;
end;
begin
readln(n,m,x);
for i:= to n do
for j:= to n do
if i=j then a[i,j]:= else a[i,j]:=maxlongint div ;
for i:= to m do
begin
readln(k1,k2,w);
a[k1,k2]:=w;
end;
dijkstra1;
for i:= to n do if i<>x then begin ans[i]:=ans[i]+d[i]; end;
dijkstra2; max:=-maxint;
for i:= to n do if i<>x then
begin
ans[i]:=ans[i]+d[i];
if ans[i]>max then max:=ans[i];
end;
writeln(max);
end.
最新文章
- #Java编程思想笔记（一）——static
- debian(kali Linux) 安装net Core
- linux部署war包方案
- matlab产生正态分布样本
- ACM ICPC Asia Regional 2011 Kuala Lumpur C题
- H264解码的一个測试程序
- 导航条——flash导航条
- 【记录一次windows技术学习】使用笔记本DOS命令搭建WLAN热点
- NV12和NV21转rgb
- Django中ORM介绍
- Netty学习笔记(二) 实现服务端和客户端
- liunx驱动----异步通知
- postgresql清理工具
- Lambda表达式遍历和泛型ForEach遍历方式
- Python开发 標準內建方法 (未完代補)
- OpenCV使用BGR而非RGB格式
- 第十节：详细讲解一下Java多线程，随机文件
- 离开(切换)当前页面时改变页面title
- jsp自定义标签开发
- Non-parseable POM 解决方法