本人是一个OIer,在做一道图论题时遇到了一个困难:为什么我和拿满分的人做法一样而我的程序却因为超时只拿了40分?
题目名称:香甜的黄油
特地前来此处请教一下各路大神:
下面是我的40分代码:
#include <iostream>
#include <cstdio>
using namespace std;
const int maxp=805,maxm=1455;
int n,p,cc,numP;
int firstEdge[maxp],nextEdge[2*maxm],weight[2*maxm],endPoint[2*maxm];
int s[505],dist[maxp],ans;
int queue[100*maxp],head,tail;
bool used[maxp];
void add(int x,int y,int w)
{
weight[++numP]=w;
endPoint[numP]=y;
nextEdge[numP]=firstEdge[x];
firstEdge[x]=numP;
}
void enqueue(int a)
{
queue[++tail]=a;
used[a]=true;
}
int pop()
{
head++;
used[queue[head]]=false;
return queue[head];
}
int main()
{
cin>>n>>p>>cc;
for(int k=1;k<=n;k++)
{
cin>>s[k];
};
int x,y,w;
for(int i=1;i<=cc;i++)
{
cin>>x>>y>>w;
add(x,y,w);
add(y,x,w);
};
ans=0xffffff;
for(int i=1;i<=p;i++)
{
head=0;tail=0;
for(int j=1;j<=p;j++)
{
dist[j]=0xffffff;
used[j]=false;
};
dist[i]=0;
enqueue(i);
int u,nowP;
while(head<tail)
{
u=pop();
nowP=firstEdge[u];
while(nowP>0)
{
if(dist[endPoint[nowP]]>dist[u]+weight[nowP])
dist[endPoint[nowP]]=dist[u]+weight[nowP];
if(!used[endPoint[nowP]])enqueue(endPoint[nowP]);
nowP=nextEdge[nowP];
};
};
int res=0;
for(int j=1;j<=n;j++)
res+=dist[s[j]];
if(res<ans)ans=res;
}
cout<<ans;
return 0;
}
这是满分代码(Pascal)
program butter;
var i,j,n,p,c,min,tot,t,x,y,z:longint;
v,next,head,cost,dis,b:array[0..3000]of longint;
team:array[0..10100]of longint;
pd:array[0..3000]of boolean;
procedure add(x,y,z:longint);
begin
inc(t);
v[t]:=y;
next[t]:=head[x];
head[x]:=t;
cost[t]:=z;
end;
procedure SPFA(x:longint);
var i,j,l,r,u,v1,e:longint;
begin
for i:=1 to p do
dis[i]:=maxlongint div 3;
l:=0;
r:=1;
team[1]:=x;
pd[x]:=true;
dis[x]:=0;
while l<>r do
begin
l:=l mod 1600+1;
u:=team[l];
pd[u]:=false;
e:=head[u];
while e<>0 do
begin
v1:=v[e];
if dis[v1]>dis[u]+cost[e] then
begin
dis[v1]:=dis[u]+cost[e];
if pd[v1]=false then begin
r:=r mod 1600+1;
team[r]:=v1;
pd[v1]:=true;
end;
end;
e:=next[e];
end;
end;
end;
begin
readln(n,p,c);
min:=maxlongint;
for i:=1 to n do
readln(b[i]);
for i:=1 to c do
begin
readln(x,y,z);
add(x,y,z);
add(y,x,z);
end;
for i:=1 to p do
begin
tot:=0;
SPFA(i);
for j:=1 to n do
tot:=tot+dis[b[j]];
if tot<min then min:=tot;
end;
writeln(min);
end.