写了三天多了……Pascal和C++分别写了spfa和dijkstra+heap……
cena手测c++最大点0.82s……pascal最大0.57s……tyvj最大点443ms……该算是过了吧……
实在不行了……求放过吧……开点时限什么的……
水平就这样了……求神牛优化……
pascal：
program heap_dijkstra;
const maxn=250010;
maxm=1200000;
inf=100000000;
type
ed=record
t,w,next:longint;
end;
heap_type=record
v,d:longint;
end;
var
heap:array[0..maxn] of heap_type;
edge:array[1..maxm] of ed;
hpos,box:array[1..maxn] of longint;
n,m,sum,hl:longint;
procedure add_edge(s,t,w:longint);
begin
inc(sum);
edge[sum].t:=t;
edge[sum].w:=w;
edge[sum].next:=box[s];
box[s]:=sum;
end;
procedure build_graph;
var i,j,w:longint;
begin
readln(n);
for i:=1 to n+1 do
begin
for j:=1 to n do
begin
read(w);
if i=1 then add_edge(n*n+1,j,w)
else if i=n+1 then add_edge((i-2)*n+j,n*n+2,w)
else add_edge((i-2)*n+j,(i-1)*n+j,w);
end;
end;
for i:=1 to n do
begin
for j:=1 to n+1 do
begin
read(w);
if j=1 then add_edge((i-1)*n+1,n*n+2,w)
else if j=n+1 then add_edge(n*n+1,i*n,w)
else add_edge((i-1)*n+j,(i-1)*n+j-1,w);
end;
end;
for i:=1 to n+1 do
begin
for j:=1 to n do
begin
read(w);
if i=1 then add_edge(j,n*n+1,w)
else if i=n+1 then add_edge(n*n+2,(i-2)*n+j,w)
else add_edge((i-1)*n+j,(i-2)*n+j,w);
end;
end;
for i:=1 to n do
begin
for j:=1 to n+1 do
begin
read(w);
if j=1 then add_edge(n*n+2,(i-1)*n+1,w)
else if j=n+1 then add_edge(i*n,n*n+1,w)
else add_edge((i-1)*n+j-1,(i-1)*n+j,w);
end;
end;
n:=n*n+2;
end;
{procedure build_graph;
var i:longint;
s,t,w:longint;
begin
readln(n,m);
for i:=1 to m do
begin
readln(s,t,w);
add_edge(s,t,w);
add_edge(t,s,w);
end;
end; }
procedure swap(a,b:longint);
begin
heap[0]:=heap[a];heap[a]:=heap[b];heap[b]:=heap[0];
hpos[heap[a].v]:=a;hpos[heap[b].v]:=b;
end;
procedure decrease(x:longint);
var i:longint;
begin
i:=x;
while (i<>1)and(heap[i].d<heap[i div 2].d) do
begin
swap(i,i div 2);
i:=i div 2;
end;
end;
procedure heapify;
var
i:longint;
begin
i:=2;
while i<=hl do
begin
if (i<hl)and(heap[i+1].d<heap[i].d) then inc(i);
if heap[i].d<heap[i div 2].d then
begin
swap(i,i div 2);
i:=i*2;
end
else break;
end;
end;
procedure relax(v,u,w:longint);
begin
if w+heap[hpos[v]].d<heap[hpos[u]].d then
begin
heap[hpos[u]].d:=heap[hpos[v]].d+w;
decrease(hpos[u]);
end;
end;
procedure dijkstra(s:longint);
var v,i,u:longint;
p:longint;
begin
for i:=1 to n do
begin
heap[i].v:=i;
heap[i].d:=inf;
hpos[i]:=i;
end;
heap[s].d:=0;
swap(1,s);
hl:=n;
while (hl>0)and(hpos[n]<=hl) do
begin
v:=heap[1].v;
swap(1,hl);
dec(hl);
heapify;
p:=box[v];
while p>0 do
begin
if hpos[edge[p].t]<=hl then relax(v,edge[p].t,edge[p].w);
p:=edge[p].next;
end;
end;
end;
begin
assign(input,'in.txt');
reset(input);
assign(output,'out.txt');
rewrite(output);
build_graph;
dijkstra(n-1);
writeln(heap[hpos[n]].d);
close(input);
close(output);
end.
c++：
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#define MAXN 250010
#define MAXM 1200000
#define inf 200000000
using namespace std;
int t[MAXM],w[MAXM],nex[MAXM],d[MAXN],v[MAXN],hpos[MAXN],box[MAXN];/*q[MAXN+1],then[MAXN+1],befo[MAXN+1],flag[MAXN+1],box[MAXN+1],dis[MAXN+1]*/
int sum,n,head,tail,i,hl;
void add_edge(int ss,int tt,int ww)
{
t[++sum]=tt;
w[sum]=ww;
nex[sum]=box[ss];
box[ss]=sum;
}
void init()
{
int i,j,ww;
sum=0;
scanf("%d",&n);
for (i=2;i<MAXN;++i)
{
d[i]=0;
box[i]=0;
}
box[1]=0;box[MAXN]=0;
for (i=1;i<=n+1;++i)
{
for (j=1;j<=n;++j)
{
scanf("%d",&ww);
if (i==1) add_edge(n*n+1,j,ww);
else if (i==n+1) add_edge((i-2)*n+j,n*n+2,ww);
else add_edge((i-2)*n+j,(i-1)*n+j,ww);
}
}
for (i=1;i<=n;++i)
{
for (j=1;j<=n+1;++j)
{
scanf("%d",&ww);
if (j==1) add_edge((i-1)*n+1,n*n+2,ww);
else if (j==n+1) add_edge(n*n+1,i*n,ww);
else add_edge((i-1)*n+j,(i-1)*n+j-1,ww);
}
}
for (i=1;i<=n+1;++i)
{
for (j=1;j<=n;++j)
{
scanf("%d",&ww);
if (i==1) add_edge(j,n*n+1,ww);
else if (i==n+1) add_edge(n*n+2,(i-2)*n+j,ww);
else add_edge((i-1)*n+j,(i-2)*n+j,ww);
}
}
for (i=1;i<=n;++i)
{
for (j=1;j<=n+1;++j)
{
scanf("%d",&ww);
if (j==1) add_edge(n*n+2,(i-1)*n+1,ww);
else if (j==n+1) add_edge(i*n,n*n+1,ww);
else add_edge((i-1)*n+j-1,(i-1)*n+j,ww);
}
}
n=n*n+2;
}
void swap(int a,int b)
{
d[0]=d[a];d[a]=d[b];d[b]=d[0];
v[0]=v[a];v[a]=v[b];v[b]=v[0];
hpos[v[a]]=a;hpos[v[b]]=b;
}
void decrease(int x)
{
int i;
i=x;
while ((i!=1)&&(d[i]<d[i>>1]))
{
swap(i,i>>1);
i=i>>1;
}
}
void heapify()
{
int i=2;
while (i<=hl)
{
if ((i<hl)&&(d[i+1]<d[i])) ++i;
if (d[i]<d[i>>1])
{
swap(i,i>>1);
i*=2;
}
else break;
}
}
void relax(int u,int v,int w)
{
if (d[hpos[v]]>d[hpos[u]]+w)
{
d[hpos[v]]=d[hpos[u]]+w;
decrease(hpos[v]);
}
}
void dijkstra(int s)
{
int p,i,V,U;
for (i=1;i<=n;++i)
{
v[i]=i;
hpos[i]=i;
d[i]=inf;
}
d[hpos[s]]=0;
swap(1,s);
hl=n;
while ((hl)&&hpos[n]<=hl)
{
V=v[1];
swap(1,hl);
--hl;
heapify();
p=box[V];
while (p)
{
if (hpos[t[p]]<=hl) relax(V,t[p],w[p]);
p=nex[p];
}
}
printf("%d\n",d[hpos[n]]);
}
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
init();
dijkstra(n-1);
return 0;
}
堆里最小的数是终点就直接退出，
我就pascal dijkstra+heap过的[/quote]
while (hl>0)and(hpos[n]<=hl) do
这句话不就是这个意思么……但是依然TLE不止……
tyvj，cena手测均可1s内AC，求RQ时限开大或加快测评机速度……管理员看一眼呐……